POJ2186 Popular Cow - Tarjan染色缩点

题目连接

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

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的时候A也崇拜C,现在要你求出那些牛是被所有的牛崇拜的。

题解

由题意可以知道当成为环的时候环内所有牛都是相互崇拜的,那么被所有牛崇拜的牛必定在一个最大的联通分量里面,并且出度为0。因为缩点后,如果出度为0的点的数目大于1的时候必定存在出度等于0的任意二者不能被对方所崇拜,与题意“被所有其他牛崇拜”不符合。同时,由于缩点后形成具有简单有向无环图,所以可以知道这个出度为0的唯一点必定可以由其他所有点得到,满足题意所述的“被所有其他牛崇拜”。所以只要输出这个出度为0的连通分量中牛的数目就可以了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 1e4+10;
vector<int> E[maxn],e[maxn];
stack<int> S;
int n,m,tag=1; //tag用来记录当前编号到哪里。
int vis[maxn],dfn[maxn],low[maxn],tot,flag[maxn],out[maxn]; //flag[i]=点编号,用于缩图,w[maxn]用于记录缩图后的点权。
int found[maxn]; //用来在寻找答案时标记已经寻找过的flag
//利用tarjan进行染色处理。
void tarjan(int x){
dfn[x]=low[x]=++tot;
vis[x]=1;
S.push(x);
for(int i=0;i<E[x].size();++i){
int v=E[x][i];
if(!dfn[v]){
tarjan(v);
low[x]=min(low[v],low[x]);
}
//访问过了不在栈中的要继续维护,即是返回边。
else if(vis[v])
low[x]=min(low[v],dfn[x]);
}
//弹到最后自己出来就已经确定好了一个连通分量。
if(low[x]==dfn[x]){
int cnt=0;
while(1){
int now = S.top();
++cnt;
vis[now]=0;
S.pop();
flag[now]=tag;
if(now==x) break;
}
++tag; //继续下一个点编号。
}
}
int main(){
scanf("%d%d",&n,&m);
int a,b;
//建立两个单向图比较快,一个记录它崇拜谁,一个是谁崇拜它(处理后找最大点)。
for(int i=0;i<m;++i){
scanf("%d%d",&a,&b);
E[a].push_back(b);
}
for(int i=1;i<=n;++i){
if(!dfn[i])
tarjan(i);
}
//Tarjan染色后进行统计操作。
for(int i=1;i<=n;++i){
for(int j=0;j<E[i].size();++j){
int v=E[i][j];
if(flag[i]!=flag[v])
++out[flag[i]];
}
}
int mark,num=0,ans=0;
for(int i=1;i<tag;++i)
if(out[i]==0)
++num,mark=i;
//如果只有一个联通分量出度为0,这里面的所有牛肯定都被其他所有牛崇拜。
if(num==1){
for(int i=1;i<=n;++i)
if(flag[i]==num)
++ans;
}
else ans=0;
printf("%d\n",ans);
}