# HDU-1811 拓扑排序(配合并查集)
## [HDU-1811](http://acm.hdu.edu.cn/showproblem.php?pid=1811)
## 题目描述
给一个编好号(0~n-1)的选手队列进行排名, 现在有m个排名信息, 分别可能是(A>B),(A=B),(A<B)其中之一.
排名规则是:
- A>B, A排更高
- A<B, B排更高
- A=B, AB中序号大的排更高
现在需要做的是判断这些信息是否可以唯一���定一个固定的排名. 有三种可能的结果:
|输出|含义|
|---:|----|
|OK|排名唯一确定|
|UNCERTAIN|信息不完全|
|CONFLICT|信息冲突|
## 分析
其实已经很明显了, 学过数据结构的人不可能不知道**拓扑排序**吧(不会吧不会吧
明确了使用拓扑排序, 我们来分析信息不完全和信息冲突分别代表着什么.
- 信息不完全, 意味着拓扑中同时出现了多个可拓扑的节点(删入弧后**入度同时为0**). 根据拓扑排序的原理, 这时的顺序可以随便取, 对本题来讲就是信息不完全了.
- 信息冲突, 意味着出现了反层次的边, 最终结果是**形成环**. 根据拓扑排序的原理, 有环图最终会剩余至少一个节点未能进行拓扑.
因此得到结论:
- 对输入的比大小数据进行图形化, **A>B生成A到B的弧**, **A<B生成B到A的弧**, A=B嘛...先放一放, 假设现在讨论的图里没有.
- 对图形进行拓扑排序. 可能出现如下三种情况:
1. 若最终拓扑节点数小于人员总数, 则一定是出现了信息冲突
2. 若拓扑途中出现了多个可拓扑的节点, 则是出现了信息不完全
3. 没有以上两点, 则排名唯一确定
现在来考虑A=B是什么. 在明确拓扑排序已经能进行A>B和A<B的排名检查后, 我们可以主动地考虑将A=B构造成拓扑排序可用的形态, 很容易想到使用**并查集**进行"缩点"(老本行了). 因此现在加入并查集, **把拓扑排序逻辑上的排序主体从节点拓展成集合**, 当然实际操作上看的是根节点.
接下来一顿傻瓜式操作, 敲代码就完事了.
## 代码
(来自[这↑里↓](https://blog.csdn.net/shuangde800/article/details/7957275))
```cpp
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 10005;
int n,m,f[N],rank[N],X[2*N],Y[2*N],son[N],t;
char O[2*N];
vector<int>G[N];
void initSet(int n){
for(int i=0; i<=n; ++i)
f[i]=i, rank[i]=0;
for(int i=0; i<=n; ++i)
G[i].clear();
memset(son, 0, sizeof(son));
}
int find(int x){
int i,j=x;
while(j!=f[j]) j=f[j];
while(x!=j){
i=f[x], f[x]=j, x=i;
}
return j;
}
bool Union(int x,int y){
int a=find(x), b=find(y);
if(a==b){
return false;
}
if(rank[a]>rank[b])
f[b]=a;
else{
if(rank[a]==rank[b])
++rank[b];
f[a]=b;
}
return true;
}
int main(){
int u,v;
char ch;
while(~scanf("%d%d",&n,&m)){
initSet(n);
int num=n;
for(int i=0; i<m; ++i){
scanf("%d %c %d",&X[i],&O[i],&Y[i]);
if(O[i]=='='){
if(Union(X[i], Y[i]))
--num;
}
}
for(int i=0; i<m; ++i)if(O[i]!='='){
int x=find(X[i]), y=find(Y[i]);
if(O[i]=='>'){
G[x].push_back(y);
son[y]++;
}
else{
G[y].push_back(x);
son[x]++;
}
}
queue<int>q;
for(int i=0; i<n; ++i){
if(son[i]==0&&i==find(i))
q.push(i);
}
int stan=0;//是否唯一
while(!q.empty()){
if(q.size()>1) stan=1;
int t=q.front();
q.pop();
--num;
for(int v=0; v<G[t].size(); ++v){
if(--son[G[t][v]]==0)
q.push(G[t][v]);
}
}
if(num>0)
printf("CONFLICT\n");
else if(stan)
printf("UNCERTAIN\n");
else
printf("OK\n");
}
return 0;
}
```
![]()