信息传递 洛谷P2661

Author Avatar
Axell 2月 06, 2019
  • 在其它设备中阅读本文章

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;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/95/