题解 P2661 【信息传递】

2017-08-15 18:21:48


本蒟蒻比较奇葩,用了个tarjan求强联通分量= =,竟然过了!!

(不过其实完全可以把不是只有一个点的强联通分量当环使)

代码长度相对来说可能不是很短,其实根本没必要打tarjan

但是tarjan很无脑,嗯嗯。按着模板敲一遍就行。不喜勿喷

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,ans=1000000;
    int sta[200001],top=0;
    int dfn[200001],low[200001],tot=0;
    int head[200001],nxt[200001],to[200001],cnt=0;
    int f[200001];
    void addedge(int x,int y)//邻接链表存图
    {
        cnt++;
        nxt[cnt]=head[x];
        head[x]=cnt;
        to[cnt]=y;
    }
    void tarjan(int u)//tarjan求强联通分量
    {
        f[u]=1;
        dfn[u]=low[u]=++tot;
        sta[++top]=u;//入栈
        for(int i=head[u];i!=0;i=nxt[i])
        {
            int v=to[i];
            if(!dfn[v])
            {
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(f[v]) low[u]=min(low[u],dfn[v]);
        }
        if(low[u]==dfn[u])
        {
            int res=0;
            do
            {
                f[sta[top]]=0;
                res++;
            }while(sta[top--]!=u);//出站并统计个数
            if(res!=1) ans=min(ans,res);//注意,一个点不算一个环,排除掉就能过啦
        }
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            addedge(i,a);//加边,是有向边,别加两次
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        cout<<ans;
        return 0;
}