信息传递 洛谷P2661 | Axell's Blog

goto

思路

任务是找到图中的一个最小环
首先，递归删除所有入度为0的点，剩下的都是环
因为每个人只有一个传输对象，因此每一个环都是独立的，直接暴力枚举即可

代码

#include <bits/stdc++.h>
using namespace std;

int n,t[200005],f[200005],tag[200005],ans=1e8;

void del(int x){
    int Next=t[x];
    f[Next]--;
    if (f[Next]==0 && t[Next]!=-1) del(Next);
    t[x]=-1;
    return;
}

void dfs(int st,int now,int len){
    tag[now]=1;
    if (now==st && len!=0){
        ans=min(ans,len);
        return;
    }
    dfs(st,t[now],len+1);
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&t[i]),f[t[i]]++;
    for (int i=1;i<=n;++i){
        if (f[i]==0 && t[i]!=-1) del(i);
    }
    for (int i=1;i<=n;++i){
        if (t[i]!=-1 && !tag[i]) dfs(i,i,0);
    }
    cout<<ans<<endl;
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/95/