# Leetcode 2360. Longest Cycle in a Graph
###### tags: `leetcode` `daily` `graph`

[題目連結](https://leetcode.com/problems/longest-cycle-in-a-graph/description/)

# Method graph
:bulb: **作法講解**:

## Concept
because every node has at most one outgoing edge,
we can easily find the circle len.

Example
:::warning
so the graph like below,

start the node from node 0
the visited order is
**`0 -> 3 -> 2 -> 4 -> 3`**

start the node from node 1
the visited order is
**`1 -> 3 -> 2 -> 4 -> 3`**

start the node from node 3
the visited order is
**`3 -> 2 -> 4 -> 3`**

start the node from node 2
the visited order is
**`2 -> 4 -> 3 -> 2`**

start the node from node 4
the visited order is
**`4 -> 3 -> 2 -> 4`**
:::

following above example,
we can summarize three features,
> 1. if the node is in circle, whatever we start from each node that in circle, always can reach start node.
>
> 2. if destination of the node is to circle, following the node edges going, always reach the node in circle.
>
> 3. if destination of the node is not to ciricle, following the node edges going, always reach -1.

## How we find the circle len
we can use `dfs` function to find the circle len,
we need a `array` to record the state the each node.

`array[i] = 0` it means the node is unvisit.
`array[i] = -1` it means the node is visited from previous round.
`array[i] = positive interger` it means the node is visited from current round.

in dfs function, we need record `depth`, initialize is 1
when we entered to next node increase `depth` by 1.

in dfs function, we may meet three case,
case 1: the node is unvisited, so set `array[node] = depth`.

case 2: the node is visited from previous round.
directly return `-1.`

case 3: if the node is visited form current round,
directly return `depth - array[node]`

TC: O(N) SC: O(N)
完整程式碼

class Solution {
public:
    int dfs(int node, int d, vector<int>& edges, vector<int> &visited) {

        if((node < 0) || (visited[node] < 0)) {
            return -1;
        }
        else if(visited[node]) {
            return d - visited[node];
        }

        int len = -1;
        visited[node] = d;
        len = dfs(edges[node], d+1, edges, visited);

        visited[node] = -1;
        return len;
    }
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        int output = -1;
        vector<int> visited(n, 0);

        for(int i = 0 ; i < n ; i++) {
            output = max(output, dfs(i, 1, edges, visited));
        }
        return output;
    }
};