<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:
    def longestCycle(self, edges: List[int]) -> int:
        # solution redone here, original solutions further below
        n = len(edges)
        incoming = [0] * n
        for v in edges:
            if v == -1:
                continue
            incoming[v] += 1
        print(incoming)
        q = collections.deque([i for i in range(n) if incoming[i] == 0])
        while q:
            u = q.popleft()
            print(u)
            v = edges[u]
            if v == -1:
                continue
            incoming[v] -= 1
            if incoming[v] == 0:
                q.append(v)
        
        print(incoming)
        res = -1
        seen = set()
        for i in range(n):
            if incoming[i] == 0 or i in seen:
                continue
            u = i
            cycle_length = 0
            while u not in seen:
                print(u)
                seen.add(u)
                u = edges[u]
                cycle_length += 1
            res = max(res, cycle_length)
            
        return res
































    #     """Solution 1:"""
    #     n = len(edges)
    #     in_degrees = [0] * n
    #     for i in range(n):
    #         if edges[i] != -1:
    #             in_degrees[edges[i]] += 1
        
    #     # do Kahn's
    #     q = collections.deque()
    #     for i in range(n):
    #         if in_degrees[i] == 0:
    #             q.append(i)
        
    #     while q:
    #         curr = q.popleft()
    #         neighbor = edges[curr]
    #         if neighbor != -1:
    #             in_degrees[neighbor] -= 1
    #             if in_degrees[neighbor] == 0:
    #                 q.append(neighbor)
        
    #     res = -1
    #     visited = [False] * n
    #     for i in range(n):
    #         if in_degrees[i] != 0 and visited[i] == False:
    #             count = 1
    #             visited[i] = True

    #             neighbor = edges[i]
    #             while neighbor != i:
    #                 visited[neighbor] = True
    #                 count += 1
    #                 neighbor = edges[neighbor]
    #             res = max(res, count)     
    #     return res           



    #     """Solution 2:"""
#     n = len(edges)
    #     seen = set()
    #     res = -1
    #     for i in range(n):
    #         if i in seen:
    #             continue
    #         seen.add(i)
    #         recurse_stack = {i: 0}
    #         res = max(res, self.dfs(i, edges, recurse_stack, seen))
    #     return res
    
    # def dfs(self, curr, edges, recurse_stack, seen):
    #     v = edges[curr]
    #     if v > -1:
    #         if v in recurse_stack:
    #             return recurse_stack[curr] - recurse_stack[v] + 1
    #         elif v not in seen:
    #             seen.add(v)
    #             recurse_stack[v] = recurse_stack[curr] + 1
    #             return self.dfs(v, edges, recurse_stack, seen)
    #     # there is a key reason why we can delete the below line
    #     # the reason is that each vertex has at most one outgoing edge
    #     # this implies that if a vertex is not on recurse_stack, then it is also
    #     # not in any of the branches coming out of the ancestor node that we started
    #     # this DFS search from in the longestCycle function.
    #     # indeed, there is only one branch from this ancestor
    #     # del recurse_stack[curr]
    #     return -1
1025