//6706173 Xredman 2186 Accepted 1496K 438MS C++ 1870B 2010-04-08 15:26:32 
/*
网上的解释很爽
算法证明：
1：假设a和b都是最受欢迎的cow，那么，a欢迎b，而且b欢迎a，于是，
	a和b是属于同一个连通分量内的点，所有，问题的解集构成一个强连通分量。
2：如果某个强连通分量内的点a到强连通分量外的点b有通路，因为b和a不是同一
	个强连通分量内的点，所以b到a一定没有通路，那么a不被b欢迎，于是a所在
	的连通分量一定不是解集的那个连通分量。
3：如果存在两个独立的强连通分量a和b，那么a内的点和b内的点一定不能互相到
	达，那么，无论是a还是b都不是解集的那个连通分量，问题保证无解。
4：如果图非连通，那么，至少存在两个独立的连通分量，问题一定无解。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_SIZE = 10002;

int n, m;
vector<int> GA[MAX_SIZE], GB[MAX_SIZE];
bool Visited[MAX_SIZE];
int post[MAX_SIZE], cnt;
int UFSet[MAX_SIZE], idcnt;
bool out[MAX_SIZE];

void init()
{
	int i;
	for(i = 1; i <= n; i++)
	{
		GA[i].clear();
		GB[i].clear();
	}
}

void dfsa(int k)
{//对逆图dfs
	Visited[k] = true;
	for(vector<int>::iterator p = GB[k].begin(); p != GB[k].end(); p++)
		if(!Visited[*p])
			dfsa(*p);
	post[cnt++] = k;
}

void dfsb(int k)
{//对原图dfs
	Visited[k] = true;
	UFSet[k] = idcnt;
	for(vector<int>::iterator p = GA[k].begin(); p != GA[k].end(); p++)
		if(!Visited[*p])
			dfsb(*p);

}

void Kosaraju()
{
	int i, j;
	int ans, flag;

	memset(Visited, 0, sizeof(Visited));
	cnt = 0;
	for(i = 1; i <= n; i++)
		if(!Visited[i])
			dfsa(i);
	idcnt = 1;
	
	memset(Visited, 0, sizeof(Visited));
	for(i = n - 1; i >= 0; i--)
		if(!Visited[post[i]])
		{
			dfsb(post[i]);
			idcnt++;
		}
	idcnt--;
	//至此求出该图由idcnt个强连通子图
	/*
	记录哪些强连通分量有出边
	*/
	memset(out, 0, sizeof(out));
	for(i = 1; i <= n; i++)
		for(vector<int>::iterator p = GA[i].begin(); p != GA[i].end(); p++)
			if(UFSet[i] != UFSet[*p])
			{
				//cout<<"XXX"<<i<<"..."<<*p<<endl;
				out[UFSet[i]] = true;
			}
	ans = 0; flag = -1;
	for(i = 1; i <= n; i++)
		if(!out[UFSet[i]])
		{
			if(flag == -1)
			{
				flag = UFSet[i];
				ans++;
			}else if(flag != UFSet[i])
			{
				flag = -2;
				break;
			}
			else
				ans++;
		}
	if(flag == -2)
		cout<<"0"<<endl;
	else
		cout<<ans<<endl;
}

int main()
{
	int a, b;
	int i;
	while(cin>>n>>m)
	{
		init();
		for(i = 0; i < m; i++)
		{
			scanf("%d%d", &a, &b);
			GA[a].push_back(b);
			GB[b].push_back(a);
		}
		Kosaraju();
	}
	return 0;
}

• 相关文章
• 全局相关文章