# 2360. Longest Cycle in a Graph
###### tags: `Leetcode` `Hard` `DFS`
Link: https://leetcode.com/problems/longest-cycle-in-a-graph/description/
## 思路
和[2359. Find Closest Node to Given Two Nodes](https://hackmd.io/rkWcS36jRWuZoBmKRuZH9g)差不多

由于每个点最多只有一个outgoing edge 其实这个图就像是一个linkedlist, current node和next node直接是straightforward的 不需要像之前一样做bfs/dfs

所以对于每个点我们顺着路线找一遍 并且把中途经历过的所有点visited设成true 如果我们在dfs的过程中碰到了之前碰到的点说明我们不用往下找了 如果我们碰到在这次dfs中遇到的点 说明有cycle cycle的大小我们只需要维持一个dist variable 记录我们到每个点走了多少距离 相减即可得到cycle的大小

一开始写的方法会TLE, 原因是对于每个node我们都有可能重新建一个memo array 然后initialize它 所以时间复杂度变成了$O(N^2)$

解决方法是
1. 用map存memo 参考[这里](https://leetcode.com/problems/longest-cycle-in-a-graph/solutions/2357650/java-dfs-hashmap/?orderBy=most_votes)
2. global memo 参考[这里](https://leetcode.com/problems/longest-cycle-in-a-graph/solutions/2357631/dfs/?orderBy=most_votes)
global memo 除了记录dist之外还要记录这个点是从哪个点开始的dfs visit到的 到了一个点发现已经visited了 并且是dfs的起始点是一样的 说明我们需要记录这个cycle 否则就不用记录
## Code
Global Memo写法

class Solution {
    public int longestCycle(int[] edges) {
        int ans = -1;
        int n = edges.length;
        int[][] memo = new int[n][2];
        for(int i=0; i<n; i++) Arrays.fill(memo[i], -1);
        for(int i=0; i<n; i++){
            for(int j=i, dist=0; j!=-1; j=edges[j]){
                int[] cur = memo[j];
                if(cur[0]==-1) memo[j]=new int[]{dist++, i};
                else{
                    if(cur[1]==i) ans = Math.max(ans, dist-cur[0]);
                    break;
                }
            }
        }
        return ans;
    }
}

TLE写法

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int longest = -1;
        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++){
            if(visited[i]) continue;
            longest = Math.max(longest, dfs(i, visited, edges));
            visited[i] = true;
        }
        return longest;
    }
    public int dfs(int node, boolean[] visited, int[] edges){
        int dist = 0;
        int n = edges.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        while(node!=-1 && memo[node]==-1 && !visited[node]){
            //if node has been visited, any cycle this node can arrive has been counted
            visited[node] = true;
            memo[node] = dist++;
            node = edges[node];
        }
        if(node!=-1) return dist-memo[node];
        else return -1;
    }
}