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; | |
| } |