[poj 2186]Popular Cows[Tarjan強連通分量]

題意:

有一群牛, a會認為b很帥, 且這種認為是傳遞的. 問有多少頭牛被其他所有牛認為很帥~

思路:

關鍵就是分析出縮點之後的有向樹只能有一個葉子節點(出度為0).

做法就是Tarjan之後縮點統計出度.

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
const int MAXE = 50005;
struct pool
{
    int v,pre;
}p[MAXE];
int num,head[MAXN];
int dfn[MAXN],low[MAXN],id[MAXN],dag[MAXN];
bool vis[MAXN];
int size,Index,n,m;
stack<int> s;
void add(int u, int v)
{
    p[++num].v = v;
    p[num].pre = head[u];
    head[u] = num;
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++Index;
    vis[u] = true;
    s.push(u);
    for(int tmp = head[u],k;k = p[tmp].v,tmp;tmp = p[tmp].pre)
    {
        if(!dfn[k])
        {
            Tarjan(k);
            low[u] = min(low[u],low[k]);
        }
        else if(vis[k])
            low[u] = min(low[u],low[k]);
    }
    if(dfn[u]==low[u])
    {
        size++;
        int k;
        do
        {
            k = s.top();s.pop();
            vis[k] = false;
            id[k] = size;
        }while(k!=u);
    }
}

void shrink()
{
    for(int i=1;i<=n;i++)
        for(int tmp = head[i],k;k = p[tmp].v,tmp;tmp = p[tmp].pre)
            if(id[i]!=id[k])
                dag[id[i]]++;//縮點
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0,u,v;i<m;i++)
    {
        scanf("%d %d",&u,&v);
        add(u, v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            Tarjan(i);
    }
    shrink();
    int ans = 0,tmp;
    for(int i=1;i<=n;i++)
    {
        if(!dag[id[i]])
        {
            if(!ans)    tmp = id[i];
            else if(tmp!=id[i])
            {
                ans = 0;
                break;
            }
            ans++;
        }
    }
    printf("%d\n",ans);
}