-
Notifications
You must be signed in to change notification settings - Fork 101
/
Find Eventual Safe states.java
45 lines (37 loc) · 1.22 KB
/
Find Eventual Safe states.java
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
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
boolean [] visited=new boolean[graph.length];
boolean [] dfsvisited=new boolean[graph.length];
HashSet<Integer> hp=new HashSet<>();
for(int i =0;i<graph.length;i++){
if(visited[i]==false){
if(isCyclic(i,graph,visited,dfsvisited,hp)){
}
}
}
List<Integer> ans=new ArrayList<>();
for(int i =0;i<graph.length;i++){
if(hp.contains(i)==true){
ans.add(i);
}
}
return ans;
}
public static boolean isCyclic(int node,int[][] graph,boolean [] visited,boolean [] dfsvisited,HashSet<Integer> hp){
visited[node]=true;
dfsvisited[node]=true;
for(int nbrs:graph[node]){
if(visited[nbrs]==false){
if(isCyclic(nbrs,graph,visited,dfsvisited,hp)){
return true;
}
}
else if(dfsvisited[nbrs]==true){
return true;
}
}
hp.add(node);
dfsvisited[node]=false;
return false;
}
}