class Solution {
int[] list;
int idx;
boolean hasCycle;
public int[] findOrder(int numCourses, int[][] prerequisites) {
int n = numCourses;
list = new int[n];
idx = n - 1;
hasCycle = false;
List<Integer>[] G = new List[n];
boolean[] visited = new boolean[n];
for (int i = 0; i < numCourses; i++) {
G[i] = new ArrayList<>();
}
for (int[] pre: prerequisites) {
G[pre[1]].add(pre[0]);
}
for (int i = 0; i < numCourses; i++) {
dfs(i, G, visited, new HashSet<>());
}
return hasCycle ? new int[0] : list;
}
private void dfs(int node, List<Integer>[] G, boolean[] visited, Set<Integer> set) {
if (set.contains(node)) {
hasCycle = true;
return;
}
if (visited[node]) return;
set.add(node);
for (int adj: G[node]) {
if (!visited[adj]) {
dfs(adj, G, visited, set);
}
}
visited[node] = true;
list[idx] = node;
idx--;
}
}
, em cập nhật ở đây với các thím cho có động lực
Đây là cách của mình thôi, chứ các thím khác có nhiều cách hiệu quả hơn.
biết v hồi đó cày dsa cho chắc r
