import java.util.*;
class Program {
public boolean cycleInGraph(int[][] edges) {
// Write your code here.
int n = edges.length;
boolean[] visited = new boolean[n];
Arrays.fill(visited, false);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
boolean containsCycle =
helper(edges, i, visited);
if (containsCycle) return true;
}
return false;
}
public boolean helper(int[][] edges, int i, boolean[] visited) {
Set < Integer > set = new HashSet < > ();
Stack < Map.Entry < Integer, Set < Integer >>> s = new Stack < > ();
set.add(i);
s.push(new AbstractMap.SimpleEntry < > (i, set));
while (!s.isEmpty()) {
Map.Entry < Integer, Set < Integer >> curr = s.pop();
Set < Integer > path = curr.getValue();
int node = curr.getKey();
visited[node] = true;
if (edges[node].length == 0) path.remove(node);
for (int children: edges[node]) {
if (visited[children] && path.contains(children)) {
return true;
}
Set < Integer > temp = new HashSet < > (path);
temp.add(children);
s.push(new AbstractMap.SimpleEntry < > (children, temp));
}
}
return false;
}
}
请确认时间和空间复杂度是O(V+E)和O(V)?
我使用了使用堆栈并将路径存储在堆栈中的迭代DFS.
我想要了解的是,在任何一点使用的空间是O(V).