P2661 [NOIP2015 提高组] 信息传递

柔光的暖阳◎ 2022-10-27 02:23 190阅读 0赞

## P2661 \[NOIP2015 提高组\] 信息传递——有向图相关算法⭐️⭐️⭐️⭐️ ##

**题目描述**  
有 n个同学（编号为 1到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti的同学。  
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？  
**输入**  
共2行。  
第1行包含1个正整数 n，表示 n个人。  
第2行包含 n个用空格隔开的正整数 T1,T2,⋯⋯,Tn，其中第 i 个整数 Ti表示编号为i的同学的信息传递对象是编号为 Ti的同学，Ti≤n且 Ti≠i。  
**输出**  
1个整数，表示游戏一共可以进行多少轮。  
**样例输入**  
5  
2 4 2 3 1  
**样例输出**  
3  
**提示**

游戏的流程如图所示。当进行完第3轮游戏后， 4号玩家会听到 2号玩家告诉他自己的生日，所以答案为 3。当然，第 3 轮游戏后，2号玩家、 3号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件.  
对于 30%的数据， n≤200；  
对于 60%的数据， n≤2500；  
对于100%的数据， n≤200000。

#include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;
    #define MAXN 200005
    #define INF 0x7FFFFFFF
    struct Edges
    { 
        int u, v, id;
    };
    struct Node
    { 
        int indegree, outdegree;
    };
    Node V[MAXN];
    int v, ans;
    vector<Edges> G[MAXN];
    bool vis[MAXN];
    void DFS(int v, int cnt)
    { 
        unsigned int i;
        if (vis[v])
        { 
            ans = min(ans, cnt);
            return;
        }
        vis[v] = true;
        for (i = 0; i < G[v].size(); i++)
            DFS(G[v][i].v, cnt + 1);
    }
    int main()
    { 
        int i, x;
        memset(V, 0, sizeof(V));
        memset(vis, 0, sizeof(vis));
        cin >> v;
        for (i = 1; i <= v; i++)
        { 
            cin >> x;
            G[i].push_back((Edges){ i, x, i}); // 存入
            V[i].outdegree++;                 // 出度加一
            V[x].indegree++;                  // 入度加一
        }
        for (i = 1; i <= v; i++)
        { 
            x = i;
            while (!V[x].indegree && !vis[x])
            { 
                vis[x] = true;
                x = G[x][0].v;
                V[x].indegree--;
            }
        }
        ans = INF;
        for (i = 1; i <= v; i++)
            if (!vis[i])
                DFS(i, 0);
        cout << ans << endl;
        return 0;
    }