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


  • 0
    B

    For example:

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

    When:
    node = 0:
    Go down: 0->1->2
    Go back: 2->1 (add:2)
    Go down: 1->3
    Go back: 3->1->0 (add:3,1,0)

    node = 1:
    isVisited = true, skip

    node = 2:
    isVisited = true, skip

    node = 3:
    isVisited = true, skip

    node = 4:
    Go down: 4->1
    isVisited = true
    Go back: 1->4 (add:4)

    node = 5:
    Go down: 5->3
    isVisited = true
    Go back: 3->5 (add:5)

    node = 6:
    Go down: 6->5
    isVisited = true
    Go back: 5->6 (add:6)

    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++)
    		{
    			adjacencyMatrix[i] = new HashSet<int>();
    		}
    
    		var isVisited = new bool[numCourses];
    
    		for(int i = 0; i < prerequisites.GetLength(0); i++)
    		{
    			var preCourse = prerequisites[i, 1];
    			var curCourse = prerequisites[i, 0];
    
    			adjacencyMatrix[preCourse].Add(curCourse);
    		}
    
    		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.Add(course);
    		    }
    		}
    
    		result.Reverse();
    
    		return result.ToArray();
        }
    
    	private int FindCourse(int curCourse, List<int> result, bool[] isVisited, HashSet<int> isVisitedForOneBranch, Dictionary<int, HashSet<int>> adjacencyMatrix)
    	{
    		foreach(var nextCourse in adjacencyMatrix[curCourse])
    		{
    		    if (isVisitedForOneBranch.Contains(nextCourse)) return -1;
    			if (isVisited[nextCourse]) continue;
    
    			isVisitedForOneBranch.Add(curCourse);
    			var course = FindCourse(nextCourse, result, isVisited, isVisitedForOneBranch,adjacencyMatrix);
    			isVisitedForOneBranch.Remove(curCourse);
    			
    			if (course == -1) return -1;
    			
    			result.Add(course);
    		}
            
            isVisited[curCourse] = true;
    		return curCourse;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.