0210-course-schedule-ii.cs

publicclassSolution{
List<int>output=null;
publicint[]FindOrder(intnumCourses,int[][]prerequisites)
{
IDictionary<int,List<int>>preMap=newDictionary<int,List<int>>();
HashSet<int>visited=newHashSet<int>();
HashSet<int>cycle=newHashSet<int>();
output=newList<int>();
for(inti=0;i<numCourses;i++)
{
preMap.Add(i,newList<int>());
}

foreach(int[]courseinprerequisites)
{
intcourseToTake=course[0];
intcourseDependOn=course[1];
preMap[courseToTake].Add(courseDependOn);
}

foreach(intcinEnumerable.Range(0,numCourses))
{
if(DfsGraphTopologicalSort(preMap,visited,cycle,c)==false)
{
returnArray.Empty<int>();
}
}
returnoutput.ToArray();
}

publicboolDfsGraphTopologicalSort(IDictionary<int,List<int>>preMap,HashSet<int>visited,HashSet<int>cycle,intcrs)
{
if(cycle.Contains(crs))returnfalse;
if(visited.Contains(crs))returntrue;

if(preMap[crs]==newList<int>())
{
returntrue;
}
cycle.Add(crs);
foreach(varpreinpreMap[crs])
{
if(DfsGraphTopologicalSort(preMap,visited,cycle,pre)==false)
{
returnfalse;
}
}
cycle.Remove(crs);
visited.Add(crs);
output.Add(crs);
returntrue;
}
}