LOJ-10091（强连通分量）

题目链接：传送门

思路：

多少头牛收到所有牛头牛的喜欢，喜欢具有传递性，所以将互相喜欢的牛视为一个点，就是有向图的

缩点，收到所有牛的喜欢要求这个“点”没有出度，所以缩点之后统计所有没有出度的点就是结果，如果有多头牛没有出度，

就说明图不连通，答案为0。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 500500;
int num[maxn],low[maxn],vis[maxn],head[maxn],ver[maxn],next[maxn],tot;
int st[maxn],out[maxn],fa[maxn],top,tim,col;
int MIN(int x,int y)
{
    return x<y?x:y;
}
int MAX(int x,int y)
{
    return x>y?x:y;
} 
void Init()
{
    memset(vis,0,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(num,0,sizeof(num));
    memset(head,0,sizeof(head));
    memset(ver,0,sizeof(ver));
    memset(next,0,sizeof(next));
    memset(st,0,sizeof(st));
    memset(out,0,sizeof(out));
    memset(fa,0,sizeof(fa));
    top=0;tim=0;tot=0;col=0;
}
void addedge(int u,int v)
{
    ver[++tot]=v;next[tot]=head[u];head[u]=tot;
}
void Tarjan(int u) //强连通模板 
{
    low[u]=num[u]=++tim;
    vis[u]=1;
    st[++top]=u;
    for(int i=head[u];i;i=next[i]){
        int v=ver[i];
        if(!vis[v]){
            Tarjan(v);
            low[u]=MIN(low[u],low[v]);
        }
        else if(!fa[v]) low[u]=MIN(low[u],num[v]);
    }
    if(low[u]==num[u]){
        fa[u]=++col;
        while(st[top]!=u){
            fa[st[top]]=col;
            top--;
        }
        top--;
    }
}
int main(void)
{
    int n,m,i,j,x,y;
    while(~scanf("%d%d",&n,&m)){
        Init();
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            addedge(x,y);
        }
        for(i=1;i<=n;i++)
        if(!vis[i]) Tarjan(i);
        
        for(i=1;i<=n;i++){
            for(j=head[i];j;j=next[j]){
                if(fa[i]!=fa[ver[j]]) out[fa[i]]++; //统计缩点后每个点的出度 
            }
        }
        x=0;
        int cnt=0,sum=0;
        for(i=1;i<=col;i++)
        if(out[i]==0) cnt++,x=i;
        if(cnt==1){ //当且仅当只有一个“点”时才有结果 
            for(i=1;i<=n;i++) //统计这个缩点中的点数 
            if(fa[i]==x) sum++;
            printf("%d
",sum);
        }
        else printf("0
");
    }
    return 0;
}