# C# solution: backtracking with the explanation to show each step's iteration

• For example:

0->1, 1->2, 1->3, 4->1, 6->5, 5->3

When:
node = 0:
Go down: 0->1->2
Go down: 1->3

node = 1:
isVisited = true, skip

node = 2:
isVisited = true, skip

node = 3:
isVisited = true, skip

node = 4:
Go down: 4->1
isVisited = true

node = 5:
Go down: 5->3
isVisited = true

node = 6:
Go down: 6->5
isVisited = true

Finished.
Reverse the result.

What if there is a dead loop:

If a branch goes down then reach any one visited node, there is a dead loop.

So using isVisitedForOneBranch to check it.

``````public class Solution
{
public int[] FindOrder(int numCourses, int[,] prerequisites)
{
var adjacencyMatrix = new Dictionary<int, HashSet<int>>();

for(int i = 0; i < numCourses; i++)
{
}

var isVisited = new bool[numCourses];

for(int i = 0; i < prerequisites.GetLength(0); i++)
{
var preCourse = prerequisites[i, 1];
var curCourse = prerequisites[i, 0];

}

var result = new List<int>();

var isVisitedForOneBranch = new HashSet<int>();

for (int i = 0; i < numCourses; i++)
{
if (!isVisited[i])
{
var course = FindCourse(i, result, isVisited, isVisitedForOneBranch, adjacencyMatrix);

if (course == -1) return new int[0];

}
}

result.Reverse();

return result.ToArray();
}

private int FindCourse(int curCourse, List<int> result, bool[] isVisited, HashSet<int> isVisitedForOneBranch, Dictionary<int, HashSet<int>> adjacencyMatrix)
{
{
if (isVisitedForOneBranch.Contains(nextCourse)) return -1;
if (isVisited[nextCourse]) continue;

var course = FindCourse(nextCourse, result, isVisited, isVisitedForOneBranch,adjacencyMatrix);
isVisitedForOneBranch.Remove(curCourse);

if (course == -1) return -1;