受欢迎的牛（Tarjan缩点模板）

雨点打透心脏的1/2处 2023-06-02 13:59 11阅读 0赞

#include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;
    
    int n,m,head[10005],vis[10005],dfn[10005],
    low[10005],color[10005],num[10005],out[10005];
    
    int sum,cnt,tot,jia,ans;
    
    stack<int> s;
    
    struct edge{
        int v,next;
    }e[50005];
    
    inline void add(int u,int v){
        e[++cnt].v=v;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    
    inline void tarjan(int u){
        vis[u]=1;
        s.push(u);
        dfn[u]=low[u]=++tot;
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[v],low[u]);
            }
            else if(vis[v])low[u]=min(low[v],low[u]);
        }
        if(dfn[u]==low[u]){
            color[u]=++sum;
            vis[u]=0;
            while(1){
                int x=s.top();
                s.pop();
                vis[x]=0;
                color[x]=sum;
                num[sum]++;
                if(x==u)break;
            }
        }
    }
    
    inline void shrink(){
        for(int u=1;u<=n;u++){
            for(int i=head[u];i!=-1;i=e[i].next){
                int v=e[i].v;
                if(color[v]!=color[u])out[color[u]]++;
            }
        }
    }
    
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])tarjan(i);
        }
        shrink();
        for(int i=1;i<=sum;i++){
            if(out[i]==0){
                jia++;
                ans=num[i];
            }
        }
        if(jia==1)printf("%d\n",ans);
        else printf("%d\n",0);
    }

# [扩展阅读：三种强联通分量算法][Link 1] #

转载于:https://www.cnblogs.com/Y15BeTa/p/11525295.html

[Link 1]: https://www.cnblogs.com/Potato-lover/p/3956604.html