# POJ 2186 Popular Cows （缩点）

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

## Output

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.

## Sample Input

3 3
1 2
2 1
2 3


## Sample Output

1


## AC 代码

#include<iostream>
#include<cstring>
#include<set>
#include<vector>
using namespace std;

const int maxn = 1e4+10;
const int maxm = 1e5+10;

struct node
{
int to;
int next;
} edge[maxm];               //原图
int fa[maxn],rk[maxn];
int dfn[maxn],low[maxn],ind;
int Stack[maxn],Stop,Bcnt;
int in[maxn];               //缩点以后反向图的入度
int BcntNum[maxn];          //每个缩点所包含原图点的个数
int color[maxn];            //原图点属于哪一个缩点
bool instack[maxn];
vector<int> G[maxn];        //缩点反向图
set<int> all_node;          //缩点集合
int n,m;

void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,false,sizeof(instack));
memset(rk,0,sizeof(rk));
memset(in,0,sizeof(in));
memset(BcntNum,0,sizeof(BcntNum));
memset(color,0,sizeof(color));
all_node.clear();
for(int i=0; i<=n; i++)
fa[i]=i;
for(int i=0; i<=n; i++)
G[i].clear();
Bcnt = Stop = ind = tot = 0;
}

{
edge[tot].to=v;
}

int find_set(int x)         //并查集查找
{
if(x!=fa[x])
fa[x]=find_set(fa[x]);
return fa[x];
}

void union_set(int x,int y)     //并查集合并
{
x=find_set(x);
y=find_set(y);
if(rk[x]<rk[y])
fa[x]=y;
else
{
fa[y]=x;
if(rk[x]==rk[y])
rk[y]++;
}
}

void tarjan(int x)
{
dfn[x]=low[x]=++ind;
instack[x]=true;
Stack[++Stop]=x;
{
int to=edge[i].to;
if(!dfn[to])
{
tarjan(to);
if(low[to]<low[x])
low[x]=low[to];
}
else if(instack[to]&&dfn[to]<low[x])
low[x]=dfn[to];
}
if (dfn[x]==low[x]) //相等说明 x 为强连通子图搜索树的根节点
{
Bcnt++;
int top,last = -1;
do  //退栈
{
top=Stack[Stop--];
if(last == -1) last = top;  //缩点该强连通分量
else union_set(last,top);
instack[top]=false;
}
while (top!=x);
}
}

void dfs(int x)         //沿着缩点后的反向图遍历
{
all_node.erase(color[x]);   //遇到的节点从缩点集合删除
for(int i=0; i<(int)G[x].size(); i++)
dfs(G[x][i]);
}

void sub_ans()
{
int last = -1;
for(set<int>::iterator i = all_node.begin(); i!=all_node.end(); i++)
if(in[*i]==0)       //查找入度为 0 的节点
last = *i;
dfs(last);
if(all_node.size())     //如果集合中还有元素，说明从 last 不能遍历到所有元素
cout<<0<<endl;
else
cout<<BcntNum[last]<<endl;
}

void solve()
{
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);
for(int i=1; i<=n; i++)
{
color[i] = find_set(i);
all_node.insert(color[i]);
BcntNum[color[i]]++;
}
for(int i=1; i<=n; i++)
{
{
int to = edge[j].to;
int f1 = find_set(i);
int f2 = find_set(to);
if(f1!=f2)
{
G[color[to]].push_back(color[i]);   //建立反向缩点图
in[color[i]]++;
union_set(f1,f2);   //合并当前这两个集合
}
}
}
sub_ans();
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n>>m)
{
init();
for(int i=0; i<m; i++)
{
int u,v;
cin>>u>>v;
}
solve();
}
return 0;
}


### 2 只已被捕捉

• heheql Chrome | 61.0.3163.100 Linux

emmmm 这题其实缩点后也不需要重建图，只要考虑出度为0的点。如果只有一个出度为0的点，直接输出这个点包含原图的点数量，否则直接输出0

http://paste.ubuntu.com/25726898/

• 千千 Mozilla FireFox | 57.0 Windows 10/11

咦 对哦~ 当时没有好好想 (*/ω＼*)，直接按照直觉写出了这个