HDU - 1811 (并查集 + 拓扑排序)

读题可以知道当成环的时候会有冲突，当不止有一个拓扑排序的时候信息不完全。

当有相等的时候可以用并查集把他们当成一个节点来处理；

代码如下：

#include<stdio.h>
#include<string.h>
#define mmset(a,b) memset(a,b,sizeof(a))
const int N = 100005;
const int M = 200005;

struct edge
{
	int x, y, flag ;
};
struct node
{
	int to,w,next;
};

node edges[M];
edge data[M];

int head[N],indegree[M],que[M],father[N] ,index = 0, que_len = 0, n , m, len = 0,sum = n,flag = 0;

void init()
{
	for(int i = 0; i <= n; i++)
	{
		father[i] = i;
	}
	mmset(head,-1);
	mmset(indegree,0);
	len = 0, sum = n, index = 0, que_len = 0,flag = 0;
	
}

void addEdge(int a, int b, int c)
{
	edges[len].to = b, edges[len].w = c;
	edges[len].next = head[a], head[a] = len++;
}

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

void merge(int fx, int fy)
{
	father[fx] = fy;
}

/*
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
*/
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		init();
		for(int i = 0; i < m; i++)
		{
			int a,b;
			char sym[2];
			scanf("%d %s %d",&a,sym,&b) ;
			if(sym[0] == '=')
			{
				int fx = find(a);
				int fy = find(b);
				if(fx != fy)  //把相等关系的节点当成一个节点来处理 
				{
					sum--;
					merge(fx,fy);
				}
				
				data[i].x = a, data[i].y = b, data[i].flag = 0;
				
			}
			else if(sym[0] == '<')
			{
				data[i].x = a, data[i].y = b, data[i].flag = 1;
			}
			else if(sym[0] == '>')
			{
				data[i].x = a, data[i].y = b, data[i].flag = 2;
			}
		}
		for(int i = 0; i < m; i++)
		{
			if(data[i].flag == 0)
			continue;
			int fx = find(data[i].x),  fy = find(data[i].y);
			if(data[i].flag == 1)
			{
				addEdge(fx,fy,1);
				indegree[fy]++;
			}
			else if(data[i].flag == 2)
			{
				addEdge(fy,fx,1);
				indegree[fx]++;
			}
		}
		for(int i = 0; i < n; i++) 
		{
			if(father[i] == i && indegree[i] == 0)  //把相等关系的节点当成一个节点来处理  
			{
				que[index++] = i;
				que_len++;
			}
		}
		
		for(int i = 0; i < index; i++)
		{
			if(que_len > 1)    //当存在多个拓扑排序的时候说明信息不完全； 
			{
				flag = 1;
			}
			int now = que[i];
			que_len--;
			sum--;
			for(int j = head[now]; j != -1; j = edges[j].next) 
			{
				indegree[edges[j].to]--;
				if(indegree[edges[j].to] == 0)
				{
					que[index++] = edges[j].to;
					que_len++;
				}
			}
			 
		}

		if(sum > 0)    //当sum > 0的时候说明会成环，这时候说明信息有冲突 
		{
			printf("CONFLICT\n");
		}
		else if(flag == 1)
		{
			printf("UNCERTAIN\n");
		}
		else
		{
			printf("OK\n");
		}
		
		
	}
	
	
	
	return 0;
}