【HDU 1811】 Rank of Tetris 并查集+拓扑
题目链接：传送门
中文题目就不阐述题意了，我最开始的想法是种类并查集，但是细想一下，发现并不可行，因为题目没有告诉有多少类型。
做法：关键问题是处理等号的两个点，其实两个点相等，就相当于这两个人的排名是一样的，我们用并查集搞定这么些个相等排名的点，之后把有全序关系的点入度入图，然后拓扑排序走一发，如果到最后所有点的度都变成了0，那么这个图就满足OK的条件，否则属于冲突。如果最后所有点的度都变成了0，但是拓扑排序期间有两个点同时度为0，那么说明信息不够全。
①先用并查集将相等的关系合并
int n,m;
while(~scanf("%d %d",&n,&m))
{
int ind[10005]= {0},peo=m; ///最终判断能否去掉所有边。（最终所有点的入度都为0）
bool vis[10005]= {0};
vector<int>load[10005];
for(int i=0; i<n; i++)
p[i]=i;
for(int i=1; i<=m; i++)
{
scanf("%d %c %d",&text[i].s,&text[i].re,&text[i].e);
if(text[i].re=='=')
{
peo--; ///相等的边去掉，其没有意义
p[f(text[i].s)]=f(text[i].e); ///让所有相等的点（排名相同的人），用一个人代替。
}
} ②利用关系入度
for(int i=1; i<=m; i++)
{
int x=f(text[i].s);
int y=f(text[i].e);
if(text[i].re=='>')
{
load[x].push_back(y);
ind[y]++;
}
if(text[i].re=='<')
{
load[y].push_back(x);
ind[x]++;
}
} ③拓扑排序+输出判断
queue<int>ranks; ///BFS拓扑
int sign=0;///入度为0的点最多一个
int ff1=1; ///判断变量 sign
for(int i=0; i<n; i++)
{
if(!vis[i]&&f(i)==i&&ind[i]==0)///入队的条件
{
sign++;
vis[i]=1;
ranks.push(i);
}
}
if(sign>1)
ff1=0;
while(ranks.size())
{
sign=0;
int w=ranks.front();
ranks.pop();
int d=load[w].size();
for(int i=0; i<d; i++)
{
peo--; ///有关系的边去除。
int e=load[w][i];
ind[e]--; ///入度减 1
if(!vis[e]&&f(e)==e&&ind[e]==0)
{
sign++;
vis[e]=1;
ranks.push(e);
}
}
if(sign>1)
ff1=0;
}
if(peo!=0) ///判断条件
printf("CONFLICT\n");
else if(ff1==0)
printf("UNCERTAIN\n");
else
printf("OK\n"); 完整的代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<set>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
int s;
char re;
int e;
} text[20005];
int p[10005];
int f(int x)
{
return p[x]==x?x:p[x]=f(p[x]);
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
int ind[10005]= {0},peo=m; ///最终判断能否去掉所有边。（最终所有点的入度都为0）
bool vis[10005]= {0};
vector<int>load[10005];
for(int i=0; i<n; i++)
p[i]=i;
for(int i=1; i<=m; i++)
{
scanf("%d %c %d",&text[i].s,&text[i].re,&text[i].e);
if(text[i].re=='=')
{
peo--; ///相等的边去掉，其没有意义
p[f(text[i].s)]=f(text[i].e); ///让所有相等的点（排名相同的人），用一个人代替。
}
}
for(int i=1; i<=m; i++)
{
int x=f(text[i].s);
int y=f(text[i].e);
if(text[i].re=='>')
{
load[x].push_back(y);
ind[y]++;
}
if(text[i].re=='<')
{
load[y].push_back(x);
ind[x]++;
}
}
queue<int>ranks; ///BFS拓扑
int sign=0;///入度为0的点最多一个
int ff1=1; ///判断变量 sign
for(int i=0; i<n; i++)
{
if(!vis[i]&&f(i)==i&&ind[i]==0)///入队的条件
{
sign++;
vis[i]=1;
ranks.push(i);
}
}
if(sign>1)
ff1=0;
while(ranks.size())
{
sign=0;
int w=ranks.front();
ranks.pop();
int d=load[w].size();
for(int i=0; i<d; i++)
{
peo--; ///有关系的边去除。
int e=load[w][i];
ind[e]--; ///入度减 1
if(!vis[e]&&f(e)==e&&ind[e]==0)
{
sign++;
vis[e]=1;
ranks.push(e);
}
}
if(sign>1)
ff1=0;
}
if(peo!=0) ///判断条件
printf("CONFLICT\n");
else if(ff1==0)
printf("UNCERTAIN\n");
else
printf("OK\n");
}
return 0;
} 
