# [POJ 2186] Popular Cows【Tarjan强连通分量】

• 2018-01-08
• 0
• 0

## Problem:

 Time Limit: 2000MS Memory Limit: 65536K

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

## Solution:

Tarjan 强连通分量缩点的模板题。Tarjan 算法参考：【转载】全网最!详!细!tarjan算法讲解

## Code: O(N+M) [688K, 79MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, M;

struct Edge{
int np;
Edge *nxt;
};

struct Graph{
Edge *V[10002], E[50002];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}
} G;

int dfn[10002], dfstime = 0;
int low[10002];
int Stack[10002], tops = 0;
int Status[10002];
int Color[10002], topc = 0, CSize[10002];

inline void Tarjan(int u){
dfn[u] = low[u] = ++dfstime;
Stack[++tops] = u, Status[u] = 1;
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
if(Status[ne->np] == 0){
Tarjan(ne->np);
low[u] = min(low[u], low[ne->np]);
}
else if(Status[ne->np] == 1) low[u] = min(low[u], dfn[ne->np]);
}
if(low[u] == dfn[u]){
topc++;
while(Stack[tops + 1] != u){
Color[Stack[tops]] = topc, CSize[topc]++;
Status[Stack[tops--]] = -1;
}
}
}

bool outdeg[10002];

int main(){
scanf("%d%d", &N, &M);
for(register int i = 1; i <= M; i++){
int u, v;
scanf("%d%d", &u, &v);
}
for(register int i = 1; i <= N; i++)
if(Status[i] == 0) Tarjan(i);
for(register int i = 1; i <= N; i++){
if(outdeg[Color[i]]) continue;
for(register Edge *ne = G.V[i]; ne; ne = ne->nxt)
if(Color[i] != Color[ne->np]){
outdeg[Color[i]] = 1;
break;
}
}
int ans = 0;
for(register int i = 1; i <= topc; i++)
if(!outdeg[i]){
if(ans) {ans = 0; break;}  // If more than 1 group doesn't admire others, there must be no cow popular to all
else ans = CSize[i];
}
printf("%d\n", ans);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai