graph, detect the longest cycle in an array
Read full article from graph, detect the longest cycle in an array
void dfs(int start, int idx, int a[], int N, bool *visited, int& len) { if(idx >= N) { | |
len = 1; | |
return; | |
} | |
visited[idx] = true; | |
len++; | |
//if(start == a[idx]) return; | |
if(visited[a[idx]] == false) { | |
dfs(start, a[idx], a, N, visited, len); | |
} | |
else if(start == idx) return; | |
} | |
int get_longest_cycle(int a[], int N) { | |
int maxlen = -1; | |
bool *visited = new bool[N]; | |
for(int i=0; i<N; i++) visited[i] = false; | |
for(int i=0; i<N; i++) { | |
if(visited[i] == false) { | |
int len = 0; | |
dfs(i, a[i], a, N, visited, len); | |
maxlen = max(maxlen, len); | |
} | |
} | |
return maxlen; | |
} | |
int main() | |
{ | |
int a[] = {1,2,8}; | |
cout << get_longest_cycle(a, 3); | |
return 0; | |
} |