-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongest Cycle
More file actions
31 lines (30 loc) · 851 Bytes
/
Copy pathLongest Cycle
File metadata and controls
31 lines (30 loc) · 851 Bytes
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
class Solution {
int len=-1;
void dfs(int cycleLen, int node, int[] currPath, int[] visited, int[] edges){
cycleLen++;
visited[node]=1;
currPath[node]=cycleLen;
int nbr=edges[node];
if(nbr!=-1){
if(visited[nbr]==0){
dfs(cycleLen,nbr,currPath,visited,edges);
}
else if(currPath[nbr]!=0){
int currLen=currPath[node]-currPath[nbr]+1;
len=Math.max(len,currLen);
}
}
currPath[node]=0;
}
public int longestCycle(int[] edges) {
int n=edges.length;
int[] visited=new int[n];
int[] currPath=new int[n];
for(int i=0; i<n; i++){
if(visited[i]==0){
dfs(0,i,currPath,visited,edges);
}
}
return len;
}
}