洛谷 P2863 [USACO06JAN]牛的舞会The Cow Prom

传送门

题目大意：形成一个环的牛可以跳舞，几个环连在一起是个小组，求几个小组。

题解：tarjian缩点后，求缩的点包含的原来的点数大于1的个数。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10009
using namespace std;

int n,m,sumedge,top,sumclr,tim,ans;
int Stack[maxn],instack[maxn],low[maxn],dfn[maxn],cnt[maxn],head[maxn];

struct Edge{
    int x,y,nxt;
    Edge(int x=0,int y=0,int nxt=0):
        x(x),y(y),nxt(nxt){}
}edge[maxn*5];

void add(int x,int y){
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}

void Tarjian(int x){
    Stack[++top]=x;instack[x]=true;
    low[x]=dfn[x]=++tim;
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].y;
        if(instack[v])low[x]=min(low[x],dfn[v]);
        else if(!dfn[v]){
            Tarjian(v);low[x]=min(low[x],low[v]);
        }
    }
    if(low[x]==dfn[x]){
        sumclr++;
        while(Stack[top+1]!=x){
            instack[Stack[top]]=false;
            cnt[sumclr]++;
            top--;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])Tarjian(i);
    for(int i=1;i<=sumclr;i++)if(cnt[i]>1)ans++;
    printf("%d
",ans);
    return 0;
}