LeetCode 2360. 图中的最长环

LeetCode 2360. 图中的最长环

基环树

class Solution {
public:
    vector<int> p;
    vector<bool> st; //是否被搜过
    vector<int> in_stk;  // 记录节点在当前栈中的深度
    int res = -1;
    void dfs(int u, int deth)
    {
        st[u] = true;
        in_stk[u] = deth;
        int ne = p[u];
        if(ne != -1)
        {
            if(in_stk[ne])
                res = max(res, deth + 1 - in_stk[ne]); // 下一个节点是已经搜过了，减去之前搜到过的深度就是环的大小
            else if(!st[ne])
                dfs(ne, deth + 1);
        }
        in_stk[u] = 0;
    }
    int longestCycle(vector<int>& edges) {
        p = edges;
        int n = edges.size();
        st = vector<bool>(n, false);
        in_stk = vector<int>(n, 0);
        for(int i = 0; i < n; i ++)
            if(!st[i])
                dfs(i, 1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31