POJ 3180 牛围着池塘跳舞 强连通分量裸题

题意：一群牛被有向的绳子拴起来，如果有一些牛（>=2）的绳子是同向的，他们就能跳跃。求能够跳跃的组数。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int  inf =0x7f7f7f7f;

const double pi=acos(-1);

const int maxn=10000;

vector<int> G[maxn+10];

int n,m,deg[maxn+10],pre[maxn+10],dfs_clock,scc_cnt,sccno[maxn+10],lowlink[maxn+10];

stack<int> S;

void tarjan(int u)

{

    pre[u]=lowlink[u]=++dfs_clock;

    S.push(u);

    for(int i=0;i<G[u].size();i++)

    {

        int v=G[u][i];

        if(!pre[v])

            {

                tarjan(v);

                lowlink[u]=min(lowlink[u],lowlink[v]);

            }

        else if(!sccno[v])

                lowlink[u]=min(lowlink[u],pre[v]);

    }

    if(lowlink[u]==pre[u])

    {

        scc_cnt++;

        while(1)

        {

            int x=S.top();S.pop();

            sccno[x]=scc_cnt;

            deg[scc_cnt]++;

            if(x==u) break;

        }

    }

}

void find_scc()

{

    MM(pre,0);MM(sccno,0);

    scc_cnt=dfs_clock=0;

    for(int i=1;i<=n;i++)

      if(!pre[i])

            tarjan(i);

}

int main()

{

    while(~scanf("%d %d",&n,&m))

    {

        for(int i=1;i<=n;i++)

            G[i].clear();

        for(int i=1;i<=m;i++)

        {

            int u,v;

            scanf("%d %d",&u,&v);

            G[u].push_back(v);

        }

        MM(deg,0);

        find_scc();

        int ans=0;

        for(int i=1;i<=scc_cnt;i++)

            if(deg[i]>=2) ans++;

        printf("%d\n",ans);

    }

    return 0;

}

　　分析：牛能一起跳舞那么他们的绳子朝向就一定是一致的，也就是形成了一个环，即一个强连通分量，

所以只要统计好整个图中元素个数>=2的强连通分量个数就好