Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- private IList<IList<int>> graph;
- private bool[] marked;
- private bool[] onStack;
- private bool hasCycle;
- private Stack<int> s;
- public int[] FindOrder(int numCourses, int[,] prerequisites) {
- graph = new List<IList<int>>();
- marked = new bool[numCourses];
- onStack = new bool[numCourses];
- s = new Stack<int>();
- for (int i = 0; i < numCourses; i++) {
- graph.Add(new List<int>());
- }
- int numEdges = prerequisites.Length >> 1;
- for (int i = 0; i < numEdges; i++) {
- graph[prerequisites[i, 1]].Add(prerequisites[i, 0]);
- }
- for (int i = 0; i < numCourses; i++) {
- if (hasCycle) break;
- if (!marked[i]) dfs(i);
- }
- return hasCycle ? new int[0] : s.ToArray();
- }
- private void dfs(int v) {
- marked[v] = true;
- onStack[v] = true;
- foreach (int w in graph[v]) {
- if (!marked[w]) dfs(w);
- else if (onStack[w]) {
- hasCycle = true;
- return;
- }
- }
- s.Push(v);
- onStack[v] = false;
- }
- }
Add Comment
Please, Sign In to add comment