在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。 先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。 一直做改操作，直到所有的节点都被分离出来。 如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。
自从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"。
本题目包含多组测试，请处理到文件结束。 每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。 接下来有M行，分别表示这些关系
对于每组测试，在一行里按题目要求输出
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
OK CONFLICT UNCERTAIN
题意：给你从1到n个人，需要给他们进行排名，已知他们部分人排名大小关系，让我我们还原整个rating顺序。
建图，把每个数字当作节点，如果遇到大于号或小于号就让排名大的节点指向小的节点（或者小指大，自己规定），然后最烦的来了——因为会出现‘=’,我们需要用到并查集合并点，两个点相等我们把它算成一个点（看成这两个点的代表），之后如果我们需要用一个点，可以通过并查集找到代表这个点的点。
另外还需判断无法排序的是因为什么状况引起的，CONFLICT是因为成环，UNCERTAIN是因为队列中有两个点，我们没有办法判断这两个点的顺序，举个简单的例子1>2,0>2,我们无法判断的0和1的顺序（因为1和0入度都是0，我们push进去的这两个数无法判断顺序）
ac代码
#include <bits/stdc++.h> using namespace std; const int maxn = 10005; int in[maxn];//存储入度 int ans[maxn];//其实不需要开ans数组（记录排序结果），我顺手写上了 vector<int> g[maxn];//邻接表存图 int fa[maxn];//并查集的数组 int n,m; int a[maxn<<1],b[maxn<<1]; char ch[maxn<<1]; int get(int x){ if(fa[x]==x)return x; else return fa[x] = get(fa[x]);//并查集的路径压缩 } void merge(int x,int y){//合并点 int p = get(x); int q = get(y); if(p!=q)fa[p] = q; } void inits(){//初始化 for(int i=0;i<n;i++)fa[i]=i; memset(ans,0,sizeof(ans)); memset(in,0,sizeof(in)); for(int i=0;i<=n;i++){ g[i].clear(); } } int main(){ while(~scanf("%d%d",&n,&m)){ inits(); for(int i=0;i<m;i++){ scanf("%d %c %d",&a[i],&ch[i],&b[i]);//这里我们注意要提前存储询问 ，并把=号的点合并 if(ch[i]=='='){ merge(a[i],b[i]); } } for(int i=0;i<m;i++){//连点 if(ch[i]=='<'){ g[get(b[i])].push_back(get(a[i])); in[get(a[i])]++; } else if(ch[i]=='>'){ g[get(a[i])].push_back(get(b[i])); in[get(b[i])]++; } } int nn=0; for(int i=0;i<n;i++){ if(fa[i]==i)nn++;//记录合并后有多少点 } queue<int>q;//下面标准的拓扑排序的板子 for(int i=0;i<n;i++){ if(in[get(i)]==0&&i==get(i)){//注意判断i与get（i） q.push(get(i)); } } int ct=0,flag=0;//ct是记录排序的点数 while(!q.empty()){ int f = q.front(); int cnt = q.size(); if(cnt>1){ flag=1;//记录是否存在一个状态，队列中有大于一个的点数，我们没有办法知道他们的顺序所以会信息不完整 } q.pop(); ans[++ct] = f; for(int i=0;i<g[f].size();i++){ int v = g[f][i]; in[v]--; if(!in[v]){ q.push(v); } } } if(ct<nn){//小于点个数说明有环是冲突 printf("CONFLICT\n"); } else { if(flag)printf("UNCERTAIN\n");// flag==1说明不完整 else printf("OK\n"); } } }