POJ 2186 Popular Cows（Targin缩点）

传送门

Popular Cows

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 31808		Accepted: 12921

Description

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is 
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow. 

Input

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow. 

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

Hint

Cow 3 is the only cow of high popularity. 

思路

题意：给出一对牛之间的羡慕关系，并且当A羡慕B，B羡慕C时，可以认为C也被A羡慕。问N头牛中，有几头牛被其他所有牛羡慕。

题解：根据样例可以看出，这个图不是DAG图，但是我们可以通过targin缩点，使之成为DAG图，对于DAG图，我们知道，如果一头牛有出度，那么它就不是被其他所有牛仰慕的牛，如果其出度为0那么其有可能成为被其他所有牛仰慕的牛，但是当出度为0的牛超过1时，便不存在被除自身外其他牛仰慕的牛，因为肯定有另外一头出度为0的牛不仰慕它。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10005;
int tot, top, scc_cnt, index;
int head[maxn], dfn[maxn], low[maxn], outde[maxn], belong[maxn], st[maxn], inst[maxn], cnt[maxn];
struct Edge
{
    int v, next;
} edge[maxn*maxn];

void init()
{
    tot = top = index = scc_cnt = 0;
    memset(head, -1, sizeof(head));memset(belong, 0, sizeof(belong));
    memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));
    memset(st, 0, sizeof(st));memset(inst, 0, sizeof(inst));
    memset(outde, 0, sizeof(outde)); memset(cnt, 0, sizeof(cnt));
}

void addedge(int u, int v)
{
    edge[tot] = (Edge)
    {
        v, head[u]
    };
    head[u] = tot++;
}

void targin(int u)
{
    int v;
    dfn[u] = low[u] = ++index;
    st[++top] = u;
    inst[u] = 1;
    for (int i = head[u];i != -1;i = edge[i].next)
    {
        v = edge[i].v;
        if (!dfn[v])
        {
            targin(v);
            low[u] = min(low[u],low[v]);
        }
        else if (inst[v])
            low[u] = min(low[u],dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        scc_cnt++;
        do
        {
            v = st[top--];
            inst[v] = 0;
            belong[v] = scc_cnt;
            cnt[scc_cnt]++;
        }
        while (u != v);
    }
}

int main()
{
    int N, M, u, v, res, sum = 0;
    init();
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    for (int i = 1; i <= N; i++)  if (!dfn[i])    targin(i);
    for (int i = 1; i <= N; i++)
    {
        for (int j = head[i]; ~j; j = edge[j].next)
        {
            int v = edge[j].v;
            if (belong[i] != belong[v])
            {
                outde[belong[i]]++;
            }
        }
    }
    for (int i = 1; i <= scc_cnt; i++)
    {
        if (!outde[i])
        {
            res = i;
            sum++;
        }
    }
    if (sum > 1)    printf("0\n");
    else    printf("%d\n", cnt[res]);
}

　　

POJ 2186 Popular Cows（Targin缩点）的相关教程结束。