[poj] 3180 the cow prom

原题

这是一道强连通分量板子题。

我们只用输出点数大于1的强连通分量的个数！

#include<cstdio>

#include<algorithm>

#include<stack>

#define N 10010

#define M 50010

using namespace std;

int n,m,head[N],dfn[N],low[N],cnt=1,t,sum,bel[N],num[N],out[N],ans;

bool instk[N];

stack <int> stk;

struct hhh

{

    int to,next;

}edge[M];

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') fu=-1,j=getchar();

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void add(int u,int v)

{

    edge[cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt++;

}

void Tarjan(int x)

{

    dfn[x]=low[x]=++t;

    stk.push(x);

    instk[x]=1;

    int v;

    for (int i=head[x];i;i=edge[i].next)

    {

	v=edge[i].to;

	if (!dfn[v])

	{

	    Tarjan(v);

	    low[x]=min(low[x],low[v]);

	}

	else if (instk[v]) low[x]=min(low[x],dfn[v]);

    }

    if (dfn[x]==low[x])

    {

	sum++;

	do

	{

	    v=stk.top();

	    stk.pop();

	    instk[v]=0;

	    bel[v]=sum;

	    num[sum]++;

	}while(v!=x);

    }

}

int main()

{

    n=read();

    m=read();

    for (int i=1,a,b;i<=m;i++)

    {

	a=read();

	b=read();

	add(a,b);

    }

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

	if (!dfn[i]) Tarjan(i);

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

	if (num[i]>1) ans++;

    printf("%d",ans);

    return 0;

}