【noip2015】信息传递

题目描述

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

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

输入

输入共 2 行。

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

第 2 行包含 n 个用空格隔开的正整数 $T^{1, T^{2, \dots \dots , T^{n ，其中第 i 个整数 T^{i 表示编号为 i 的同学的信息传递对象是编号为}}}}$

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

输出

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

样例输入

5
2 4 2 3 1

样例输出

对于 30%的数据， n ≤ 200；

对于 60%的数据，n ≤ 2500；

对于 100%的数据，n ≤ 200000。

题解

化简下题意：给出一个n个点的有向图，每个点有且只有一条出边，求图中的最小环。

我们记录每个点的入度，将入度为0的点全部删掉（不可能成环），删除的时候要将当前删除的点连向的点的入度减1。

删除完之后图中就只剩下环。于是我们就可以愉快的dfs找最小环了。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=200000+50;
const int inf=0xffffff;

int n,t[maxn],ans=inf,fat[maxn],pre[maxn],post[maxn],Tim,in[maxn];
bool p[maxn];

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

void del(int x){
    int v=t[x];
    t[x]=0;
    in[v]--;
    if(in[v]==0) del(v);
}

void dfs(int u,int &T){
    p[u]=true;
    int v=t[u];
    pre[u]=++T;
    if(!p[v]) dfs(v,T);
    post[u]=++T;
}

int main(){
    read(n);
    for(int i=1;i<=n;i++) read(t[i]),in[t[i]]++;
    for(int i=1;i<=n;i++) if(!in[i]) del(i);
    for(int i=1;i<=n;i++){
        if(!p[i]&&in[i]){
            Tim=0;
            dfs(i,Tim);
            ans=min(ans,(pre[i]+post[i]-1)/2);
        }
    }
    cout<<ans<<endl;
    return 0;
}

tarjan求强连通分量：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=200000+50;
const int inf=2e9+7;

int n,a[maxn],dfn[maxn],low[maxn],stack[maxn],col[maxn],sum,deep;
bool vis[maxn];
int fir[maxn],to[maxn],nex[maxn],ecnt,cnt[maxn],t,ans=inf;

void add_edge(int u,int v){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;
}

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

int tarjan(int u){
    dfn[u]=++deep;
    low[u]=deep;
    vis[u]=1;
    stack[++t]=u;
    for(int e=fir[u];e;e=nex[e]){
        int v=to[e];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(vis[v]) low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        col[u]=++sum;
        vis[u]=0;
        while(stack[t]!=u){
            col[stack[t]]=sum;
            vis[stack[t--]]=0;
        }
        t--;
    }
}

int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),add_edge(i,a[i]);
    for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
    cnt[col[i]]++;
    for(int i=1;i<=sum;i++)
    if(cnt[col[i]]!=1) ans=min(ans,cnt[col[i]]);
    cout<<ans<<endl;
    return 0;
}