POJ2186 Popular Cows（Tarjan缩点）

Popular Cows

Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 37696
Accepted: 15354

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

Hint

Cow 3 is the only cow of high popularity.

Source

USACO 2003 Fall

链接

http://poj.org/problem?id=2186

题意

给定一个n点m边有向图，问有多少个点满足规则：可以被其他任意点访问，也就是其他任意点都有路径到达该点。

题解

使用Taijan求强连通分量，然后缩点得到DAG图，点权为为强联通分量中点的个数，有且只有一个点的出度为0时才符合要求，答案为该点点权。

具体可以参考gungnir__的详细解释：传送门。

代码

Status	Accepted
Time	516ms
Memory	2500kB
Length	2229

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 10010;
vector <int> E[maxn];
vector <int> G[maxn];
int n, m;
int tot, scc_cnt;

int dfn[maxn], low[maxn], sccno[maxn], sccnum[maxn], outde[maxn];
bool vis[maxn];
stack <int> s;

void tarjan(int x) // 求强连通分量
{
    dfn[x] = low[x] = ++tot;
    s.push(x);
    vis[x] = true;
    for (int i = 0; i < G[x].size(); ++i)
    {
        int v = G[x][i];
        if (!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (vis[v])
            low[x] = min(low[x], dfn[v]);
    }
    if (dfn[x] == low[x])
    {
        ++scc_cnt;
        while (1)
        {
            int u = s.top();
            s.pop();
            vis[u] = 0;
            sccno[u] = scc_cnt;
            sccnum[scc_cnt]++;
            if (u == x)
                break;
        }
    }
}

void find_scc()
{
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(vis));
    memset(low, 0, sizeof(low));
    memset(sccno, 0, sizeof(sccno));
    memset(sccnum, 0, sizeof(sccnum));
    tot = scc_cnt = 0;
    for (int i = 0; i < n; ++i)
        if (!dfn[i])
            tarjan(i);
}

int main()
{
    int u, v;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i <= n; ++i)
        {
            G[i].clear();
            E[i].clear();
        }
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            u--;
            v--;
            G[u].push_back(v);
        }
        find_scc();
        memset(outde, 0, sizeof(outde));
        for (int u = 0; u < n; ++u) // 缩点建图
        {
            for (int i = 0; i < G[u].size(); ++i)
            {
                int v = G[u][i];
                if (sccno[u] != sccno[v])
                    outde[sccno[u]]++;
            }
        }
        int ans, num = 0;
        for (int i = 1; i <= scc_cnt; ++i)
        {

            if (outde[i] == 0)
            {
                num++;
                ans = sccnum[i];
            }
        }
        if (num == 1)
            printf("%d\n", ans);
        else
            printf("0\n");
    }
    return 0;
}

直接在板子的基础上改了下，没想到一次过了，开心。

The end.
2018-04-24 星期二