[Rank of Tetris]拓撲排序+并查集
拓撲排序概述
在一個有向圖中，對所有的節點進行排序，要求沒有一個節點指向它前面的節點，
先統計所有節點的入度，對于入度為0的節點就可以分離出來，然后把這個節點指向的節點的入度減一，
一直做改操作，直到所有的節點都被分離出來，
如果最后不存在入度為0的節點，那就說明有環，不存在拓撲排序，也就是很多題目的無解的情況，
Problem Description
自從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"，
input
本題目包含多組測驗，請處理到檔案結束，
每組測驗第一行包含兩個整數N,M(0<=N<=10000,0<=M<=20000),分別表示要排名的人數以及得到的關系數，
接下來有M行，分別表示這些關系
output
對于每組測驗，在一行里按題目要求輸出
Sample Input
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
Sample Output
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");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162790.html
標籤：java