sundeepblue
5/15/2014 - 5:36 PM

graph, detect the longest cycle in an array

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