首先，因为会出现二个数相等情况，需要通过并查集合并为一个集合。如果不能进行拓扑排序将会出现“CONFLICT”这种情况，这也就等价为根本找不到入度为0的节点，或者为遍历完所有节点就出现找不到入度为0的节点了。还有就是一次找到多于1个的入度为0的节点，这就会出现“UNCERTAIN”这种情况了。对这二种情况分别考虑就可以了。

//2188531 2010-03-15 19:59:23 Accepted 1811 31MS 668K 2427 B C++ 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int N = 10003;

typedef struct
{
	int parent;//记录前驱
	int height;//记录集合树高度
}Node;

Node UFSet[N];
vector<int> V[N];
int vv[N][2];
int degree[N];

int n;//表示要排名的人数
int m;//得到的关系数


int find(int x)
{
	while(x != UFSet[x].parent)
	{
		x = UFSet[x].parent;
	}
	return x;
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);

	if(x == y)
		return;
	//合并操作应使树尽量平衡，即将深度小的树合并到深度大的树
	if(UFSet[x].height == UFSet[y].height)
	{
		UFSet[y].parent = x;
		UFSet[x].height++;
	}else if(UFSet[x].height > UFSet[y].height)
	{
		UFSet[y].parent = x;
	}else
	{
		UFSet[x].parent = y;
	}
}
int main()
{
	int lv, rv;
	int i, cc, znode, kk;//cc记录不相等的关系有cc对
	int res;//0:OK; 1:CONFLICT; 2:UNCERTAIN
	char op;
	vector<int>::iterator p;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		//init
		for(i = 0; i < n; i++)
		{
			UFSet[i].parent = i;
			UFSet[i].height = 1;
			V[i].clear();
		}
		memset(degree, 0, sizeof(degree));
		res = 0;
		cc = 0;
		for(i = 0; i < m; i++)
		{
			scanf("%d %c %d", &lv, &op, &rv);
			if(op == '=')
			{
				merge(lv, rv);
			}
			else
			{
				if(op == '<')
				{
					swap(lv, rv);
					
				}vv[cc][0] = lv; vv[cc++][1] = rv;
			}
		}

		for(i = 0; i < cc; i++)
		{//邻接表构图
			lv = find(vv[i][0]);
			rv = find(vv[i][1]);
			V[lv].push_back(rv);
			degree[rv]++;
		}
		queue<int> Q;
		znode = 0;//记录入度为0的节点个数
		for(i = 0; i < n; i++)
		{
			if(degree[i] == 0 && find(i) == i)
			{
				Q.push(i);
				znode++;
			}
		}
		if(znode == 0)
		{//优先级最高，立刻停止以下动作
			res = 1;//有环，冲突
		}else
		{
			if(znode > 1)
				res = 2;
			while(!Q.empty())
			{
				kk = Q.front();
				Q.pop();
				znode = 0; degree[kk]--;
				for(p = V[kk].begin(); p != V[kk].end(); p++)
				{
					degree[*p]--;
					if(degree[*p] == 0)
					{
						Q.push(*p);
						znode++;
					}
				}
				if(znode > 1)
					res = 2;
			}
			
		}
		for(i = 0; i < n; i++)
			if(degree[i] > 0)
			{
				res = 1;
				break;
			}
		if(res == 0)
			cout<<"OK"<<endl;
		else if(res == 1)
			cout<<"CONFLICT"<<endl;
		else if(res == 2)
			cout<<"UNCERTAIN"<<endl;
		//0:OK; 1:CONFLICT; 2:UNCERTAIN
	}
	return 0;
}

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