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

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

<p>Return <em>the length of the <strong>longest</strong> cycle in the graph</em>. If no cycle exists, return <code>-1</code>.</p>

<p>A cycle is a path that starts and ends at the <strong>same</strong> node.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/08/graph4drawio-5.png" style="width: 335px; height: 191px;" />
<pre>
<strong>Input:</strong> edges = [3,3,4,2,3]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-1.png" style="width: 171px; height: 161px;" />
<pre>
<strong>Input:</strong> edges = [2,-1,3,1]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There are no cycles in this graph.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-1 &lt;= edges[i] &lt; n</code></li>
	<li><code>edges[i] != i</code></li>
</ul>

class Solution {
public:
        
/*
    Pseudo intuition:
        * THERE WILL BE AT MOST 1 CYCLE FOR EACH CONNECTED COMPONENT
        * BECUASE OF THE CONDITION : 
                each node has at most one outgoing edge. 
                think of reversing the edges : after reversing each node will have atmost one incoming edge.
                                                for a tree(IN A CONNECTED COMPONENT), if add an extra edge from a
                                                node to a root, then this will happen and this will add only one cycle

        1. use DFS to find the cycle length of each component
        2. Compare the length of cycles for each connected components
*/



    vector<vector<int>> adj;
    vector<bool> dfsStarted, dfsFinished;
    vector<int> parent;

    // returns cycle length
    int dfs(int u) {
        // printf("\nu=%d", u);
        dfsStarted[u] = true;
        for (int v: adj[u]) {
            if (dfsStarted[v] && !dfsFinished[v]) {
                // cycle found
                int len = 1;
                for (int x = u; x != v; x = parent[x]) 
                    ++len;

                dfsFinished[u] = true;
                return len;
            } else if (!dfsStarted[v]) {
                parent[v] = u;
                int len = dfs(v);
                if (len != 0) {
                    dfsFinished[u] = true;
                    return len;
                }
            }
        }
        // printf("\ndfs finsihed: %d", u);
        dfsFinished[u] = true;
        return 0;
    }

    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        adj = vector<vector<int>>(n);
        for (int u = 0; u < n; ++u) {
            int v = edges[u];
            if (v != -1) adj[u].push_back(v);
        }
        dfsStarted = vector<bool>(n, false);
        dfsFinished = vector<bool>(n, false);
        parent = vector<int>(n, -1);
        
        int res = -1;
        for(int u = 0; u < n; u++) {            
            if(!dfsStarted[u]) {
                res = max(res, dfs(u));
            }
        }
        return res == 0 ? -1 : res;

    }
};
203425