hdu 1811
题目大意：
有n个点，m个序关系，关系只有三种表示方式：a < b , a > b , a = b，问根据给定的关系能否将n个点排成有序，能输出OK，若两点之间出现 a < b 且 b < a 的情况，则输出CONFLICT，若出现某些点间的关系不确定，则输出UNCERTAIN，若后两者同时存在，则优先输出CONFLICT。
题目分析：
由于存在 a = b 的情况，所以需要用并查集，将所有相等的点进行缩点，然后进行拓扑排序，注意！优先输出CONFLICT。
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 10010
using namespace std;
vector<int>g[N];
int rank[N], f[N], m,n,num[N], save[20005][2], q[N];
int find(int x)//并查集的查找函数
{
if(f[x]==x) return x;
else return f[x]=find(f[x]); //路径压缩，而且这样写对汇编源码有优化，不容易因递归层数太多出现栈溢出，但仅是不易！
}
void Union(int x, int y)//并查集的合并操作
{
int a=find(x);
int b=find(y);
if(a!=b){
if(rank[a]<rank[b]) //通过判断两个集合的大小，将小集合并入大集合，减少递归层数，算是个优化
f[a]=b, rank[b]+=rank[a];
else
f[b]=a, rank[a]+=rank[b];
}
}
int main()
{
int i,j,k,a,b,ans,tmp,x,y,tim;
char s[5];
while(scanf("%d %d",&n,&m)!=EOF){
for(i=0; i<=n; i++){
f[i]=i;
g[i].clear();
rank[i]=1;
}
memset(num, 0, sizeof(num));
k=0;
for(i=0; i<m; i++){
scanf("%d %s %d",&a, s, &b);
if(s[0]!='='){
if(s[0]=='>'){
tmp=a;
a=b;
b=tmp;
}
save[k][0]=a, save[k++][1]=b;
}
else if(s[0]=='='){
Union(a, b);
}
}
for(i=0; i<k; i++){
x=find(save[i][0]);
y=find(save[i][1]);
g[x].push_back(y);
num[y]++;
}
ans=0;
int head=0, tail=0; //从这里开始拓扑排序，用队列做保险啊，直接写的话很容易错
k=0;
for(i=0; i<n; i++)
if(num[i]==0 && find(i)==i){ //找到第一轮入度（num[]）为零的点入队。
q[tail++]=i;
k++;
}
if(k==0)
ans=2;
else{
if(k>1) ans=1; //本题要求
while(head<tail){ //排序过程
x=q[head++]; num[x]=-1; k=0;
for(i=0; i<g[x].size(); i++){
y=g[x][i];
num[y]--;
if(num[y]==0)
q[tail++]=y, k++;
}
if(k>1) ans=1; //本题要求
}
for(i=0; i<n; i++) //本题要求
if(num[i]>0){
ans=2;
break;
}
}
if(ans==0)
printf("OK\n");
else if(ans==1)
printf("UNCERTAIN\n");
else if(ans==2)
printf("CONFLICT\n");
}
return 0;
}