【题解】#2272 信息传递

非常悲哀，代码高亮无了@admin

解法一

题意很清楚，求图中最小的环。

如果一个人的入度为0，则肯定不可能成环，那么把这个人和他连出的边删去（即标记这个人并将他下一个人的入度减 1），

如果下一个人的入度为0则将他也删去……最后把所有入度为0的人都删去了，剩下的都是环。

每个人的出度为1，所以每个人只能在一个环中，每条边只能在一个环中，也就是说每个环都是分开的，

然后进行一遍 dfs，找出最小的环。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int n,t[200050],d[200050],ans=1000000000,r[200050];
void read(int& x){
    x=0;
    int y=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') y=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*y;
}
void dfs(int ti,int s,int l){
    if (ti==s&&l){ //如果回到开始说明连成了环 
        ans=min(ans,l);
        return;
    }
    if (!d[t[ti]]) {
        d[t[ti]]=1;  //标记 
        dfs(t[ti],s,l+1);
    }
}
void rmove(int ti){//删除ti 
    d[ti]=-1; //标记 
    r[t[ti]]--;  //ti的下一个人的入度减一 
    if (!r[t[ti]]&&d[t[ti]]!=-1) rmove(t[ti]);
}
int main(){
    freopen("ferry.in","r",stdin);
    freopen("message.out","w",stdout);
    memset(d,0,sizeof(d));
    memset(r,0,sizeof(r));//r[i]为第 i 个人的入度 
    int i;
    read(n);
    for (i=1;i<=n;i++){
        read(t[i]);
        r[t[i]]++;
    }
    for (i=1;i<=n;i++){
        if (!r[i]&&d[i]!=-1) rmove(i);//如果 i 的入度为 0 且还未被删除，则删除i 
    }
    for (i=1;i<=n;i++){
        if (!d[i]){     //如果i还未搜过且未被删除，则从i开始搜索 
            //cout<<i<<' ';
            dfs(i,i,0);
        }
    }
    //cout<<endl;
    printf("%d",ans);
    return 0;
}

解法二

把每个同学看成一个点，信息的传递就是在他们之间连有向边，游戏轮数就是求最小环。

图论求最小环，我在里面看到了并查集。

假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。

这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。

如果有两个点祖先节点相同，那么就可以构成一个环，长度为两个点到祖先节点长度之和+1。

#include<cstdio>
#include<iostream>
using namespace std;
int f[200002],d[200002],n,minn,last;   //f保存祖先节点，d保存到其祖先节点的路径长。 
int fa(int x)
{
    if (f[x]!=x)      //查找时沿途更新祖先节点和路径长。 
    {
        int last=f[x];       //记录父节点（会在递归中被更新）。 
        f[x]=fa(f[x]);        //更新祖先节点。 
        d[x]+=d[last];     //更新路径长（原来连在父节点上）。 
    }
    return f[x];
}
void check(int a,int b)
{
    int x=fa(a),y=fa(b);               //查找祖先节点。 
    if (x!=y) {f[x]=y; d[a]=d[b]+1;}//若不相连，则连接两点，更新父节点和路径长。 
    else minn=min(minn,d[a]+d[b]+1);//若已连接，则更新最小环长度。 
    return;
}
int main()
{
    int i,t;
    scanf("%d",&n);
    for (i=1;i<=n;i++) f[i]=i;//祖先节点初始化为自己，路径长为0。
    minn=0x7777777;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&t);
        check(i,t);//检查当前两点是否已有边相连接。 
    }
    printf("%d",minn);
    return 0;
}