hdu1811 链表的最重要 非常很好的模板式链表拓扑排序

#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;
#define max 20005
int pre[max],las[max],parent[max],in[max];
char f[max];
struct edge
{
	int val;
	struct edge *next;
}*e[10005];
int find_root(int x)//并查集
{
	return x==parent[x]?x:find_root(parent[x]);
}
void add(int x,int y)
{
    struct edge *p;
	p=(struct edge *)malloc(sizeof(struct edge));
	p->val=y;
	p->next=e[x];
	e[x]=p;
}
int main()
{
	int n,m,i,num,x,y,flag;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		flag=0;
		for(i=0;i<n;i++)//初始化
		{
			parent[i]=i;
			in[i]=0;
			e[i]=NULL;
		}
		num=n;//num是需要排序的点的个数 
		for(i=0;i<m;i++)
		{
			scanf("%d %c %d",&pre[i],&f[i],&las[i]);
			if(f[i]=='=')//把所有相等的合并到一条链上去
			{
				x=find_root(pre[i]);
				y=find_root(las[i]);
				if(x!=y)
				{
					parent[x]=y;
					num--;
				}
			}
		}
		for(i=0;i<m;i++)
		{
			if(f[i]=='=') continue;
			x=find_root(pre[i]);
			y=find_root(las[i]);
			if(x==y) { flag=1;break;}//看是否有输入的与等于号起冲突  排序的时候只抽出根 链上其他的就不管了 但是要看下有没有产生矛盾与其它点
			if(f[i]=='>')
			{
				// add(pre[i],las[i]);
				// in[las[i]]++;
				/*由于上面的原因错了好多次  以至于对比着人家的代码都找不出错误 还是WA   主要原因是还不理解题目的做法 本题是把相等的全部
				放进一条链里面 然后排序的时候 只把这些链的根拿出来当代表去排序 因此当加入边的时候加入的是所有链的根节点（把不含相等
				的点作为一条单独只有一个节点的链） 所以要用并查集找出来链的根 对根进行操作
				*/
				add(x,y);
				in[y]++;
			}
			if(f[i]=='<')
			{
				// add(las[i],pre[i]);
				// in[pre[i]]++;
				add(y,x);
				in[x]++;
			}
		}
		if(flag)
		{
			printf("CONFLICT\n");
			continue;
		}
		priority_queue<int>duilie;
		for(i=0;i<n;i++)
		{
			if(in[i]==0&&i==find_root(i))//i==find_root(i) 才能保证是根
				duilie.push(i);
		}
		while(!duilie.empty())
		{
			if(duilie.size()>1) flag=1;// 等于1 就说明有2个入度为0的点 有多条路 应该输出UNCERTAIN
			num--;//每一次进入相当于排好了一个点
			x=duilie.top();
			duilie.pop();
			while(e[x]!=NULL)//干掉所有以它开头的边
			{
				if(--in[e[x]->val]==0) //一直减下去 对于原本为0的点 就变成了-1 可以防止已经排过的点再次入队
					duilie.push(e[x]->val);
				e[x]=e[x]->next; 
			}
		}
		if(num>0) printf("CONFLICT\n");
		else if(flag) printf("UNCERTAIN\n");
		else printf("OK\n");
	}
	return 0;
}
/* 本题是把相等的全部放进一条链里面 然后排序的时候 只把这些链的根拿出来当代表去排序
因此当加入边的时候加入的是所有链的根节点（把不含相等的点作为一条单独只有一个节点的链）
所以要用并查集找出来链的根 对根进行操作*/
/*
讲一下拓扑排序的一些小知识
如果一次入队入度为零的点大于1则说明拓扑排序序列不唯一
如果排序的总个数小于给定的个数,则说明存在回路
*/
参考过的http://972169909-qq-com.iteye.com/blog/1052820;