C# solution: graph, BFS


  • 0
    B
    	public class Solution
    	{
    		public bool CanFinish(int numCourses, int[,] prerequisites)
    		{
    		    if (numCourses == 0) return true;
    		    
    			var adjacencyMatrix = new Dictionary<int, HashSet<int>>();
    
    			var inDegrees = new int[numCourses];
    
    			for (int i = 0; i < numCourses; i++)
    			{
    				adjacencyMatrix[i] = new HashSet<int>();
    			}
    
    			for (int i = 0; i < prerequisites.GetLength(0); i++)
    			{
    				var preCourse = prerequisites[i, 1];
    				var curCourse = prerequisites[i, 0];
    
    				adjacencyMatrix[preCourse].Add(curCourse);
    				inDegrees[curCourse]++;
    			}
    
    			var isVisited = new HashSet<int>();
    
    			var queue = new Queue<int>();
    
    			for(int i = 0; i < inDegrees.Length; i++)
    			{
    				if (inDegrees[i] == 0)
    				{
    					queue.Enqueue(i);
    					isVisited.Add(i);
    				}
    			}
    
    			while (queue.Any())
    			{
    				var size = queue.Count;
    
    				for (int s = 0; s < size; s++)
    				{
    					var cur = queue.Dequeue();
                        inDegrees[cur]--;
    
    					foreach (var course in adjacencyMatrix[cur])
    					{
    						inDegrees[course]--;
    
    						if (isVisited.Contains(course)) return false;
    					}
    				}
    
    				for(int i = 0; i < inDegrees.Length; i++)
    			    {
    				    if (inDegrees[i] == 0)
                        {
    					    isVisited.Add(i);
    					    queue.Enqueue(i);
                        }
    				}
    			}
    
                if (inDegrees.Any(c => c != -1)) return false;
    
    			return true;
    		}
    	}
    

Log in to reply
 

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