lp2661 NOIP2015 信息传递

找图上最小环。删掉所有非环边即可。

#include<iostream>
#include<cstdio> 
struct ee{
    int v;
    int nxt;
}e[200005];
int h[200005],et=0;
bool vis[200005];
int n,in[200005],a[200005];
inline void add(int u,int v){
    e[++et]=(ee){v,h[u]};
    h[u]=et;
}
inline int fnd(int s){
    int x=s,nxt=a[x],rt=1;
    vis[x]=1;
    while(!vis[nxt]){
        ++rt;
        x=nxt;
        nxt=a[nxt];
        vis[x]=1;
    }
    return rt;
}
void init(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        add(i,x);
        ++in[x];
        a[i]=x;
    }
    int nw,nwxt;
    for(int i=1;i<=n;++i){
        nw=i;
        while(!in[nw]){
            --in[a[nw]];
            nwxt=nw;
            nw=a[nw];
            a[nwxt]=0;
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        if(!vis[i]&&a[i]){
            ans=std::min(ans,fnd(i));
        }
    }
    printf("%d\n",ans);
}

int main(){
    init();
    return 0;
}