You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1.

Return the length of the longest cycle in the graph. If no cycle exists, return -1.

A cycle is a path that starts and ends at the same node.

&nbsp;
Example 1:

Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The longest cycle in the graph is the cycle: 2 -&gt; 4 -&gt; 3 -&gt; 2.
The length of this cycle is 3, so 3 is returned.


Example 2:

Input: edges = [2,-1,3,1]
Output: -1
Explanation: There are no cycles in this graph.


&nbsp;
Constraints:


	n == edges.length
	2 &lt;= n &lt;= 105
	-1 &lt;= edges[i] &lt; n
	edges[i] != i


class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        preorder = [-1 for _ in range(len(edges))]
        self.ans = -1
        self.pre = 0
        
        def dfs(self, i: int, st: int) -> None:
            preorder[i] = self.pre
            self.pre += 1
            
            if edges[i] == -1:
                return
            elif preorder[edges[i]] == -1:
                dfs(self, edges[i], st)
                return
            elif preorder[edges[i]] >= st:
                self.ans = max(self.ans, preorder[i] - preorder[edges[i]] + 1)
                return
        
        for i in range(len(edges)):
            if preorder[i] == -1 and edges[i] != -1:
                dfs(self, i, self.pre)
        
        return self.ans
class Solution {
    public int longestCycle(int[] edges) {
        int[] map = new int[edges.length];
        int result = -1;

        for (int i = 0; i < edges.length; i++)
            result = Math.max(result, helper(i, 1, edges, map));

        return result;
    }

    int helper(int index, int total, int[] edges, int[] map) {
        if (index == -1 || map[index] == -1)
            return -1;

        if (map[index] != 0)
            return total - map[index];

        map[index] = total;
        int result = helper(edges[index], total + 1, edges, map);
        map[index] = -1;

        return result;
    }
}
class Solution {
public:
    
    int maxLength = -1;
    
    void getcycle(vector<int> &edges,int si,vector<bool>& visit,vector<int>& store){
        if(si == -1)return ;
        if(visit[si]){
            int count = -1;
            for(int i =0;i<store.size();i++){
                if(store[i]==si){
                    count = i;
                    break;
                } }
            
            if(count==-1)return;
            int size = (store.size()-count);
            maxLength = max(maxLength,size);
            return ;
        }
        
        visit[si] = true;
        store.push_back(si);
        getcycle(edges,edges[si],visit,store);
        
        
        return ;
        
    }
    
    
    
    int longestCycle(vector<int>& edges) {
        
        vector<bool> visit(edges.size(),0);
        
        for(int i =0;i<edges.size();i++){
            
            if(visit[i])continue;
            vector<int> store;
            getcycle(edges,i,visit,store);
     
        }
        
        return maxLength;
        
    }
};
/**
 * @param {number[]} edges
 * @return {number}
 */
function getCycleTopology(edges){
    const indeg = new Array(edges.length).fill(0);
    const queue = [];
    const map = {};
    for(const src in edges){
        const des = edges[src]
        if(des >= 0){
            indeg[des] ++;
        }
        map[src] ? map[src].push(des) : map[src] = [des]
    }
    for(const node in indeg){
        if(indeg[node] === 0){
            queue.push(node)
        }
    }
    while(queue.length > 0){
        const node = queue.shift();
        for(const connectedNode of map[node]){
            if(connectedNode !== -1){
                indeg[connectedNode] --;
                if(indeg[connectedNode] === 0){
                    queue.push(connectedNode);
                }
            }
        }
    }
    return indeg
}
class DisjointSet{
    constructor(n){
        this.n = n;
        this.root = new Array(n).fill(0).map((_,i) => i);
        this.rank = new Array(n).fill(1);

    }
    find(x){
        if(x === this.root[x]) return x;
        return this.root[x] = this.find(this.root[x]);
    }
    union(x,y){
        const x_root = this.find(x);
        const y_root = this.find(y);

        if(this.rank[x_root] < this.rank[y_root]){
            [this.rank[x_root] , this.rank[y_root]] = [this.rank[y_root] , this.rank[x_root]];
        }
        this.root[y_root] = x_root;
        if(this.rank[x_root] === this.rank[y_root]) this.rank[x_root] ++;
    }
    _getGroupsComponentCounts(){
        let groups = {};
        for(const node of this.root){
            const node_root = this.find(node);
            groups[node_root] = groups[node_root] +1 || 1
        }
        return groups
    }
    getLongestGroupComponentLength(){
        let longestLength = 1;
        const lengths = this._getGroupsComponentCounts();
        for(const length of Object.values(lengths)){
            if(length > 1){
                longestLength = Math.max(longestLength, length);
            }
        }
        return longestLength > 1 ? longestLength : -1;
    }
}
var longestCycle = function(edges) {
    const djs = new DisjointSet(edges.length);
    let res = -1

    // topology sort results topology array.
    // component with greater than 0 is cyclic component.
    // now we need to get groups of cycle since we can't distinguish each cycles with current datas.
    const cycleComponent = getCycleTopology(edges); 

    //with edges info and cycle component data, we can now distinguish each cycle group by union finde
    // because each cycle r independent with each other.
    for(const src in edges){
        const des = edges[src];
        if(cycleComponent[src] && cycleComponent[des]){
            djs.union(src, des);
        }
    }
    res = djs.getLongestGroupComponentLength()
    return res
};
Longest Cycle in a Graph