[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算法讲解

只需要用奶牛之间的好感关系建立有向图的模型,那么每个强连通分量的奶牛可以看做是内部互相有好感的一个群体。Tarjan 缩点之后,受所有奶牛欢迎的群体就不能有出边。因为其他的每个奶牛群体都能直接或间接地到达该群体,若该群体有出边,则它们可以构成一个强连通分量,这与缩点后的图是 DAG 矛盾。

如果有多个群体没有出边,则这些群体之间相互不可达,即此时没有受所有奶牛欢迎的奶牛,答案为 0。

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);
		G.addedge(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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai