There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
1 public class Solution { 2 public bool CanFinish(int numCourses, int[,] prerequisites) { 3 4 var dependencies = new List<int>[numCourses]; 5 6 for (int i = 0; i < prerequisites.GetLength(0); i++) 7 { 8 int c = prerequisites[i, 0], d = prerequisites[i, 1]; 9 10 // a course is dependent on itself 11 if (c == d) return false; 12 13 if (dependencies[c] == null) dependencies[c] = new List<int>(); 14 15 dependencies[c].Add(d); 16 } 17 18 var visited = new bool[numCourses]; 19 var done = new bool[numCourses]; 20 21 for (int i = 0; i < numCourses; i++) 22 { 23 if (!DFS(new bool[numCourses], done, dependencies, i)) 24 { 25 return false; 26 } 27 } 28 29 return true; 30 } 31 32 private bool DFS(bool[] visited, bool[] done, List<int>[] dependencies, int c) 33 { 34 if (done[c]) return true; 35 if (visited[c]) return false; 36 37 visited[c] = true; 38 39 if (dependencies[c] == null) 40 { 41 done[c] = true; 42 return true; 43 } 44 else 45 { 46 foreach (var d in dependencies[c]) 47 { 48 if (!DFS(visited, done, dependencies, d)) return false; 49 } 50 51 done[c] = true; 52 return true; 53 } 54 } 55 }
转载于:https://www.cnblogs.com/liangmou/p/7918533.html
