1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] tp = new int[numCourses];
List<Edge> edges = new ArrayList<Edge>();
for(int i=0; i<prerequisites.length; i++) {
edges.add(new Edge(prerequisites[i][0],prerequisites[i][1]));
}
Graph graph = new Graph(edges, numCourses);
if (!isDAG(graph, numCourses))
return new int[]{};
List<Integer> tplist = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
boolean visited[] = new boolean[numCourses];
for (int i = 0; i < numCourses; i++)
visited[i] = false;
for (int i = 0; i < numCourses; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack, graph);
while (stack.empty() == false)
tplist.add( stack.pop() );
Collections.reverse(tplist);
for(int i=0; i<tplist.size();i++)
tp[i] = tplist.get(i);
return tp;
}
void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack, Graph graph) {
visited[v] = true;
Integer i;
Iterator<Integer> it = graph.adjList.get(v).iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack, graph);
}
stack.push(new Integer(v));
}
public boolean isDAG(Graph graph, int N) {
boolean[] discovered = new boolean[N];
int[] departure = new int[N];
int time = 0;
for (int i = 0; i < N; i++)
if (discovered[i] == false)
time = DFS(graph, i, discovered, departure, time);
for (int u = 0; u < N; u++) {
for (int v : graph.adjList.get(u)) {
if (departure[u] <= departure[v])
return false;
}
}
return true;
}
private int DFS(Graph graph, int v, boolean[] discovered, int[] departure, int time) {
discovered[v] = true;
for (int u : graph.adjList.get(v)) {
if (!discovered[u])
time = DFS(graph, u, discovered, departure, time);
}
departure[v] = time++;
return time;
}
}
class Edge {
int source, dest;
public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}
public class Graph {
List<List<Integer>> adjList = null;
Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
for (Edge edge : edges) {
adjList.get(edge.source).add(edge.dest);
}
}
}
|