MENU

POJ2186 Popular Cows(Tarjan缩点)

2018 年 04 月 24 日 • 阅读: 2646 • 图论阅读设置

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

1

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__的详细解释:传送门

代码

StatusAccepted
Time516ms
Memory2500kB
Length2229
#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 星期二
最后编辑于: 2018 年 07 月 14 日