POJ 2186 Popular Cows （缩点）

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.

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 31 22 12 3

Sample Output

1

题意

查找图中有多少个点，满足其他所有点都可以直接或者间接到达该点。

思路

首先，我们可以想到，最终的结果可能出现在原图的一个强连通子图中。

因此，对原图进行缩点，缩点以后的图是一个有向无环图，而此时，要想某个节点可以被其他任意点直接或者间接到达，则该点一定可以沿着反向边到达图中任意节点。

于是我们考虑反向建立缩点图，然后寻找一个入度为 0 的点开始 dfs ，若无法到达缩点图中其他所有点，则结果为 0$0$ ，否则结果为起始点中所包含的所有原图点的个数。

AC 代码

#include#include#include#includeusing namespace std;const int maxn = 1e4+10;const int maxm = 1e5+10;struct node{ int to; int next;} edge[maxm]; //原图int head[maxn],tot;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 G[maxn]; //缩点反向图set all_node; //缩点集合int n,m;void init(){ memset(head,-1,sizeof(head)); 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;}void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++;}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]::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<>n>>m) { init(); for(int i=0; i>u>>v; addedge(u,v); } solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。