POJ 2186 Popular Cows 强连通分量

链接：http://poj.org/problem?id=2186

题意：给出若干对大牛A仰慕大牛B，并且仰慕可以传递，问有多少个大牛被除本身之外的所有大牛仰慕。

思路：先tarjan缩点，找出每个强连通分量出度和入度，如果有强连通分量出度入度都为零或者有超过一个强连通分量的出度为零，就没有大牛满足条件，否则答案就是出度为零的强连通分量的结点数。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#define PI acos(-1.0)
#define maxn 10005
#define INF 1<<25
#define MAX 0x7fffffff
#define mem(a,b) memset(a,b,sizeof(a))
#define f(i,a,b) for(i=a;i<b;i++)
typedef long long ll;
using namespace std;
struct Edge
{
    int v;
    int next;
} edge[maxn*5];
int dfn[maxn],low[maxn],ou[maxn],in[maxn],head[maxn],ins[maxn],belong[maxn],num[maxn];
int top,cnt,t,v,i,ans;
int add_edge(int u,int v)
{
    edge[top].v=v;
    edge[top].next=head[u];
    head[u]=top++;
}
int init()
{
    mem(head,-1);
    mem(dfn,0);
    mem(ou,0);
    mem(in,0);
    mem(ins,0);
    mem(num,0);
    top=cnt=t=ans=0;
}
stack <int> S;
int tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    S.push(u);
    ins[u]=1;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        v=edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]&&dfn[v]<low[u])
            low[u]=dfn[v];
    }
    if(low[u]==dfn[u])
    {
        t++;
        do
        {
            v=S.top();
            belong[v]=t;
            num[t]++;
            ins[v]=0;
            S.pop();
        }
        while(u!=v);
    }
}
int main()
{
    int tot,tt;
    scanf("%d%d",&tot,&tt);
    init();
    f(i,0,tt)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
    }
    f(i,1,tot+1)
    if(!dfn[i])
        tarjan(i);
    f(i,1,tot+1)
    {
        int a=belong[i];
        for(int j=head[i]; j!=-1; j=edge[j].next)
        {
            int b=belong[edge[j].v];
            if(a!=b)
            {
                ou[a]++;
                in[b]++;
            }
        }
    }
    int jud=0,jud1=0;
    if(t==1)
        printf("%d\n",tot);
    else
    {
        f(i,1,t+1)
        {
            if(in[i]==ou[i]&&in[i]==0)
                jud=1;
            else if(ou[i]==0)
            {
                ans+=num[i];
                jud1++;
            }

        }
        if(!jud&&jud1<=1)
            printf("%d\n",ans);
        else printf("0\n");
    }
}

POJ 2186 Popular Cows 强连通分量,布布扣,bubuko.com

POJ 2186 Popular Cows 强连通分量

原文：http://blog.csdn.net/ooooooooe/article/details/20946263