hdu1811 并查集+拓扑排序

Rank of Tetris

自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。

为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排。

终于，Lele要开始行动了，对N个人进行排名。为了方便起见，每个人都已经被编号，分别从0到N-1,并且编号越大，RP就越高。
同时Lele从狗仔队里取得一些（M个）关于Rating的信息。这些信息可能有三种情况，分别是"A > B",“A = B”,“A < B”，分别表示A的Rating高于B,等于B,小于B。

现在Lele并不是让你来帮他制作这个高手榜，他只是想知道，根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。
注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。

Input
本题目包含多组测试，请处理到文件结束。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系

Output
对于每组测试，在一行里按题目要求输出

Sample Input

3 3
0 > 1
1 < 2
0 > 2
4 4
1 = 2
1 > 3
2 > 0
0 > 1
3 3
1 > 0
1 > 2
2 < 1

Sample Output

OK
CONFLICT
UNCERTAIN

思路：最关键的地方就是在两个人成绩相等时如何处理，考虑一个问题
正确的排序结果中如果有若干个成绩相同的，则可以用其中一个代替其他相同的数
例如A>B,B=C,C>D, 则结果为A>B=C>D,缩减为A>C>D,则原题目可以近似为A>C,C>D(即有B的地方都用C代替) ，这一思路，可以使用并查集来实现，所有相同的点使用同一个跟节点来实现。构建缩减图后，使用拓扑排序即可。

判断信息不完全：拓扑排序一个队列中同时存在两个值，则可以有多种排序方式，则信息不完整
判断冲突：如果A->B,B->A，即拓扑序列的个数小于总数

并查集

int find(int x)
{
	if(x!=father[x])
		father[x]=find(father[x]);
	return father[x];
}

void Union(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
	{
		if(x<y) swap(x,y);
		father[x]=y; //最小的数作为根节点
		sum--; //结合起来，然后总结点数减一 
	}
}

拓扑排序

void Topo(int n)
{
	queue<int> myQ;
	for(int i=0;i<n;i++)
		if(inDegree[i]==0&&father[i]==i)
		myQ.push(i);
	int num=0;
	int flag=0;
	while(!myQ.empty())
	{
		int u=myQ.front();
		myQ.pop();
		num++;
		if(myQ.size()>=1)  flag=1;
		for(int i=0;i<graph[u].size();i++)
		{
			int v=graph[u][i];
			inDegree[v]--;
			if(inDegree[v]==0)
			myQ.push(v);
		}
	}
	if(num<sum) printf("CONFLICT\n");  //入度为0的找不到，不能构成拓扑排序，冲突 
	else if(flag==1) printf("UNCERTAIN\n");
	else printf("OK\n");
}

完整代码

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std;
const int MAXN=10000;
const int MAXM=20000;
int father[MAXN];
int inDegree[MAXN];
vector<int> graph[MAXN];
int from[MAXM];
int to[MAXM];
char link[MAXM];
int sum;
void Initial(int n)
{
	for(int i=0;i<n;i++)
	father[i]=i;
	memset(inDegree,0,sizeof(inDegree));
	memset(graph,0,sizeof(graph));
} 
int find(int x)
{
	if(x!=father[x])
		father[x]=find(father[x]);
	return father[x];
}

void Union(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
	{
		if(x<y) swap(x,y);
		father[x]=y; 
		sum--; //结合起来，然后总结点数减一 
	}
}
void Topo(int n)
{
	queue<int> myQ;
	for(int i=0;i<n;i++)
		if(inDegree[i]==0&&father[i]==i)
		myQ.push(i);
	int num=0;
	int flag=0;
	while(!myQ.empty())
	{
		int u=myQ.front();
		myQ.pop();
		num++;
		if(myQ.size()>=1)  flag=1;
		for(int i=0;i<graph[u].size();i++)
		{
			int v=graph[u][i];
			inDegree[v]--;
			if(inDegree[v]==0)
			myQ.push(v);
		}
	}
	if(num<sum) printf("CONFLICT\n");  //入度为0的找不到，不能构成拓扑排序，冲突 
	else if(flag==1) printf("UNCERTAIN\n");
	else printf("OK\n");
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		Initial(n);
		sum=n;
		for(int i=0;i<m;i++)//记录所有，并且把相等的两个节点合并 
		{
			scanf("%d %c %d",&from[i],&link[i],&to[i]);
			if(link[i]=='=')
			{
				Union(from[i],to[i]);
			}
		}
		for(int i=0;i<m;i++)
		{
			int fa=find(from[i]);
			int fb=find(to[i]);
			if(link[i]=='>')
			{
				graph[fa].push_back(fb);
				inDegree[fb]++;
			}
			if(link[i]=='<')
			{
				graph[fb].push_back(fa);
				inDegree[fa]++;
			}
		}
		
		Topo(n);
	}
	return 0;
}

注意点：1、每次合并需要把总数减一（用于判断是否构成拓扑序列）
2、相等的数中最小的数作为根节点，（任意一个节点就行，然后把其他所有节点对应的关系转移到根节点）