d******4
发帖数: 132 | 1 需要检测graph是否有cycle吧？leetcode将这题放到BFS里面, 用BFS怎么做？ | r****7
发帖数: 2282 | 2 具体是啥？
【在 d******4 的大作中提到】
: 需要检测graph是否有cycle吧？leetcode将这题放到BFS里面, 用BFS怎么做？
| w***y
发帖数: 6251 | 3 用BFS的话，是不是需要把visited edge都删掉？ | s******x
发帖数: 417 | 4 使用queue
凡是indegree == 0的，入queue，然后找接下去的相连点，indegree减一。
【在 w***y 的大作中提到】
: 用BFS的话，是不是需要把visited edge都删掉？
| a**x
发帖数: 14 | 5 class Solution {
public:
bool canFinish(int numCourses, vector>& prerequisites) {
// 0..n-1
vector vis(numCourses, false);
vector > mp(numCourses, vector());
vector ind(numCourses);
// init the map
for (int i = 0; i < prerequisites.size(); i++) {
int x = prerequisites[i][0];
int y = prerequisites[i][1];
mp[x].push_back(y);
ind[y]++;
}
queue que;
int tsort = 0;
for (int i = 0; i < numCourses; i++) {
if (ind[i] == 0) {
que.push(i);
tsort++;
}
}
while(!que.empty()) {
int n = que.front(); que.pop();
for (int i = 0; i < mp[n].size(); i++) {
ind[mp[n][i]]--;
if (ind[mp[n][i]] == 0) {
que.push(mp[n][i]);
tsort++;
}
}
}
return tsort == numCourses;
}
}; | n**e
发帖数: 116 | 6 public class Solution {
private final Map> adj = new HashMap<>();
public boolean canFinish(int numCourses, int[][] prerequisites) {
for (int i = 0; i < prerequisites.length; ++i) {
int u = prerequisites[i][0], v = prerequisites[i][1];
addEdge(u, v);
}
boolean[] visited = new boolean[numCourses];
boolean[] recursionStack = new boolean[numCourses];
for (Integer v : adj.keySet()) {
if (hasCycle(v, visited, recursionStack)) return false;
}
return true;
}
private void addEdge(int u, int v) {
if (!adj.containsKey(u)) {
adj.put(u, new LinkedList<>());
}
adj.get(u).add(v);
if (!adj.containsKey(v)) {
adj.put(v, new LinkedList<>());
}
}
private boolean hasCycle(int v, boolean[] visited, boolean[]
recursionStack) {
if (!visited[v]) {
visited[v] = true;
recursionStack[v] = true;
for (Integer u : adj.get(v)) {
if (!visited[u] && hasCycle(u, visited, recursionStack))
return true;
else if (recursionStack[u]) return true;
}
}
recursionStack[v] = false;
return false;
}
} |
|
