# 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.

3 3
1 2
2 1
2 3

1

### Hint

Cow 3 is the only cow of high popularity.

USACO 2003 Fall

### 链接

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

### 代码

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 星期二

1. 可以说是非常棒了@(真棒)

1. @CongTsang#(害羞)