Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sundeepblue/ec4b012800ec0994648a to your computer and use it in GitHub Desktop.
Save sundeepblue/ec4b012800ec0994648a to your computer and use it in GitHub Desktop.
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment