基环树与拓扑排序技巧

基环树的基本知识： https://www.cnblogs.com/fusiwei/p/13815549.html

题目1： 《参加会议的最多员工数》

本题属于内向基环树。并且用到了通过拓扑排序将基环和树枝分离开的技巧：

详细方法见：灵茶山艾府题解

AC代码：

const int N = 100010;
class Solution {
public:
    int h[N], e[N], ne[N], idx;
    int din[N];

    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }

    int maximumInvitations(vector<int>& fav) {
        int n = fav.size();
        memset(h, -1, sizeof h);
        for(int i = 0; i < n; i++){
            add(i, fav[i]);
            din[fav[i]]++;
        }

        //topsort剪掉树枝
        int q[N], hh = 0, tt = -1;
        int dist[N];
        for(int i = 0; i < n; i++) dist[i] = 0;
        for(int i = 0; i < n; i++)
            if(din[i] == 0) q[++tt] = i;

        while(hh <= tt){
            auto t = q[hh++];
            for(int i = h[t]; ~i; i = ne[i]){
                int j = e[i];
                dist[j] = dist[t] + 1;
                if(--din[j] == 0) q[++tt] = j;
            }
        }
        
        int mxring = 0, mxsl = 0;
        for(int i = 0; i < n; i++){
            if(din[i] == 0) continue;
            int ring = 1;  //当前基环长度
            din[i] = 0;
            for(int v = fav[i]; v != i; v = fav[v]){
                din[v] = 0;
                ring++;
            }
            if(ring == 2) mxsl += dist[i] + dist[fav[i]] + 2;
            else mxring = max(mxring, ring);
        }
        return max(mxring, mxsl);
    }   
};

题目2： 《图中最长环》

const int N = 100010;
class Solution {
public:
    bool st[N];
    int in_stk[N];
    int dist[N];
    int ans = -1;
    vector<int> p;
    vector<int> path;
    void dfs(int u, int d){
        in_stk[u] = d;
        st[u] = true;
        int x = p[u];
        if(x != -1){
            if(!st[x]) dfs(x, d + 1);
            else if(in_stk[x]){  //找到一个环
                ans = max(ans, d + 1 - in_stk[x]);
                //拓展：
                //如果要求输出环的信息，那么可以在找到环的同时，再跑一遍环即可，代码如下所示：

                // path.clear();
                // path.push_back(x);
                // int y = p[x];
                // while(y != x){
                //     path.push_back(y);
                //     y = p[y];
                // }
                // for(auto& c : path) printf("%d ", c);
                // puts("");
            }
        } 
        in_stk[u] = 0;
    }

    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        this->p = edges;
        for(int i = 0; i < n; i++){
            if(!st[i]) dfs(i, 1);
        } 
        return ans;
    }
};