6730628 Xredman 2186 Accepted 1268K 485MS C++ 2055B 2010-04-12 11:09:49

//6730628 Xredman 2186 Accepted 1268K 485MS C++ 2055B 2010-04-12 11:09:49 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

const int MAX_SIZE = 10002;

int n, m;
vector<int> G[MAX_SIZE];
int UFSet[MAX_SIZE];
bool instack[MAX_SIZE];
int bcnt, dindex;
int dfn[MAX_SIZE], low[MAX_SIZE];
stack<int> Stack;
bool out[MAX_SIZE];

void init()
{
	int i;
	for(i = 1; i <= n; i++)
	{
		G[i].clear();
		UFSet[i] = i;//并查集判强连通集合
		low[i] = i;
	}
	while(!Stack.empty())
		Stack.pop();
	memset(instack, false, sizeof(instack));
}

void tarjan(int x)
{
	int j;
	dfn[x] = low[x] = ++dindex;
	instack[x] = true;
	Stack.push(x);
	for(vector<int>::iterator iter = G[x].begin(); iter != G[x].end(); iter++)
	{
		j = *iter;
		if(!dfn[j])
		{
			tarjan(j);
			if(low[j] < low[x])
				low[x] = low[j];
		}
		else if(instack[j] && dfn[j] < low[x])
			low[x] = dfn[j];
	}

	if(dfn[x] == low[x])
	{
		bcnt++;
		do
		{
			j = Stack.top();
			Stack.pop();
			instack[j] = false;
			UFSet[j] = bcnt;
		} while(x != j);
	}
}

void solve()
{
	int i;
	memset(dfn, 0, sizeof(dfn));
	for(i = 1; i <= n; i++)
		if(!dfn[i])
			tarjan(i);
}


int main()
{
	int a, b;
	int i;
	int ans, flag;
	while(cin>>n>>m)
	{
		init();
		for(i = 0; i < m; i++)
		{
			scanf("%d%d", &a, &b);
			G[a].push_back(b);
		}
		solve();
	/*	for(i = 1; i <= n; i++)
			cout<<UFSet[i]<<" ";*/
		///////////////////////////////////////
		memset(out, 0, sizeof(out));
		for(i = 1; i <= n; i++)
			for(vector<int>::iterator iter = G[i].begin(); iter != G[i].end(); iter++)
				if(UFSet[i] != UFSet[*iter])
				{
					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 = -1;
					break;
				}
				else
					ans++;
			}
		if(flag == -1)
			cout<<"0"<<endl;
		else
			cout<<ans<<endl;
	}
	return 0;
}

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