POJ2186 Popular Cows 强连通分量tarjan

做这题主要是为了学习一下tarjan的强连通分量，因为包括桥，双连通分量，强连通分量很多的求法其实都可以源于tarjan的这种方法，通过一个low,pre数组求出来。

题意：给你许多的A->B ,B->C这样的喜欢的关系，A->B ,B->C也意味着A->C,最后问你被全部别的人喜欢的cow有多少个。如果不告诉你用强连通分量，感觉可能会绕的远一些，但是如果知道了这个思路其实是很显然的。

首先是跑出每个强连通分量，在这种情况下，原来的图就变成了一棵树，一棵有有向边的树，然后不难发现，如果这棵树存在一个出度为0的点，那么它就很有可能是答案，为什么是可能呢？因为我们不知道是不是所有别的点都有路径连到它这里，所以判断的方法有这么几种吧。理论上如果只有1个出度为0的点应该就是答案了。还有一个是反向建图，然后从这个出度为0的点深搜，如果每个点都被搜到的话就说明这个点是可行的。

tarjan的算法大白书上有，具体不做过多的介绍，下面的代码有两种判断的，第一种简单，不用建图只需要统计出度，第二种复杂。在这道题了如果用Kosaraju算法会好过第二种，因为它搜出的强连通分量是按拓扑序的，tarjan则是不按的，所以用Kosaraju算法可以很容易求出那个出度为0的点。

#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<stack>
#define maxn 10050
using namespace std;

vector<int> G[maxn + 50];
int n, m;

int out[maxn + 50];
int sccno[maxn + 50]; // 属于哪个强连通分量
int sccSize[maxn + 50];
int scc_cnt; // 强连通分量的数量

int pre[maxn + 50];
int low[maxn + 50];
int dfs_clock;
stack<int> S;

int dfs(int u)
{
	int lowu = pre[u] = ++dfs_clock;
	S.push(u);
	for (int i = 0; i < G[u].size(); i++){
		int v = G[u][i];
		if (!pre[v]){
			int lowv = dfs(v);
			lowu = min(lowu, lowv);
		}
		else if (!sccno[v]){
			lowu = min(lowu, pre[v]);
		}
	}
	if (lowu == pre[u]){
		scc_cnt++;
		while (1){
			int x = S.top(); S.pop();
			sccno[x] = scc_cnt;
			sccSize[scc_cnt]++;
			if (x == u) break;
		}
	}
	return low[u] = lowu;
}

void find_scc()
{
	memset(sccno, 0, sizeof(sccno));
	memset(pre, 0, sizeof(pre));
	memset(sccSize, 0, sizeof(sccSize));
	memset(low, 0, sizeof(low));
	while (!S.empty()) S.pop();
	dfs_clock = scc_cnt = 0;
	for (int i = 1; i <= n; i++){
		if (!pre[i]) dfs(i);
	}
}

vector<int> NG[maxn + 50];

void constructNG()
{
	memset(out, 0, sizeof(out));
	for (int i = 0; i <= scc_cnt; i++) NG[i].clear();
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < G[i].size(); j++){
			int u = i, v = G[i][j];
			if (sccno[v] != sccno[u]){
				out[sccno[u]]++;
				NG[sccno[v]].push_back(sccno[u]);
			}
		}
	}
}

void ndfs(int u)
{
	pre[u] = 1;
	for (int i = 0; i < NG[u].size(); i++){
		ndfs(NG[u][i]);
	}
}

int main()
{
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++) G[i].clear();
		int u, v;
		for (int i = 0; i < m; i++){
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
		}
		find_scc();
		constructNG();
		int foo = -1; int outnum = 0;
		for (int i = 1; i <= scc_cnt; i++){
			if (out[i] == 0){
				foo = i; outnum++;
			}
		}
		bool flag = true;
		/*memset(pre, 0, sizeof(pre));
		ndfs(foo);
		bool flag = true;
		for (int i = 1; i <= scc_cnt; i++){
			if (!pre[i]){
				flag = false; break;
			}
		}*/
		if (outnum != 1) flag = false;
		int ans = 0;
		if (!flag) {
			puts("0"); 
			continue;
		}
		printf("%d
", sccSize[foo]);
	}
	return 0;
}