信息传递【NOIP2015】【强连通分量 Tarjan】

题目链接

题目描述

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为Ti的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮?

输入描述:

第 1 行包含 1 个正整数 n，表示 n 个人。

第 2 行包含 n 个用空格隔开的正整数T1,T2, … … ,Tn，其中第 i 个整数Ti表示编号为 i 的同学的信息传递对象是编号为Ti的同学，Ti≤ n 且Ti≠ i。

数据保证游戏一定会结束。

输出描述:

1个整数，表示游戏一共可以进行多少轮。

  因为，每个回合大家都会告诉下一个人信息，那么只要构成环的时候就是结束游戏了，所以直接去找最小环的边数即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, to[maxN];
int dfn[maxN], low[maxN], tot, Belong[maxN], Bcnt, Stop, Stap[maxN], siz[maxN];
bool instack[maxN];
void Tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    instack[u] = true;
    Stap[++Stop] = u;
    int v = to[u];
    if(!dfn[v])
    {
        Tarjan(v);
        low[u] = min(low[u], low[v]);
    }
    else if(instack[v] && dfn[v] < low[u]) low[u] = dfn[v];
    if(dfn[u] == low[u])
    {
        Bcnt++;
        do
        {
            v = Stap[Stop--];
            Belong[v] = Bcnt;
            instack[v] = false;
            siz[Bcnt]++;
        }while(u != v);
    }
}
int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &to[i]);
    for(int i=1; i<=N; i++) if(!dfn[i]) Tarjan(i);
    int ans = INF;
    for(int i=1; i<=Bcnt; i++)
    {
        if(siz[i] > 1)
        {
            ans = min(ans, siz[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}