【NOIP2015】信息传递(tarjan)

题目链接：http://uoj.ac/problem/146

 

题目大意：每个人都有信息传递对象，每一轮一个人传给下一个人，问多少轮以后有人能从别人那听到自己的信息。

 

题目思路：即强联通分量中点的数量不为1的最小值是多少。tarjan的原理是维护dfn和low数组，当下一个点的low比自己小的时候就说明自己的儿子或自己能到达可以到达自己的点(自己的祖先)，那么也就形成了环。形成环就形成了一个强联通分量。

 

以下是代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 2e5+5;
int x,n,dfn[MAXN],low[MAXN],vis[MAXN],ans,tot;
vector<int>g[MAXN];
stack<int>s;
void tarjan(int u){
    low[u]=dfn[u]=++tot;
    s.push(u);
    vis[u]=1;
    int len=g[u].size();
    rep(i,0,len-1){
        int v=g[u][i];
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int num=0;
        while(1){
            num++;
            int now=s.top();
            s.pop();
            vis[now]=0;
            if(now==u)break;
        }
        if(num>1)ans=min(ans,num);
    }
}
int main(){
    while(~scanf("%d",&n)){
        tot=0;
        ans=inf;
        while(!s.empty())s.pop();
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(vis,0,sizeof(vis));
        rep(i,1,n)g[i].clear();
        rep(i,1,n){
            scanf("%d",&x);
            g[i].push_back(x);
        }
        rep(i,1,n){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}