题意:现在有一个排名系统,有一系列信息,分别是 > < = 的比较,而如果最终相等,就会将这些相等的按照序号从小到大排,问给出的信息是否可以确定完整的排序。
由于如果很多点相等,他们肯定能够确定名次,那么我们只要让他们共同拥有与其他点的大小关系就行了。所以就用到了并查集,将相等的点加入并查集,再对并查集排拓扑序,如果能够排出唯一的拓扑序,那么在每个并查集内部也能够有唯一的顺序。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=1e4+5; 6 const int maxm=2e4+5; 7 8 int fa[maxn],num,n; 9 int a[maxm],b[maxm];10 char c[maxm][10];11 int head[maxn],point[maxm],nxt[maxm],size;12 int id[maxn];13 14 void init(){ for(int i=0;i