Rank of Tetris
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3671 Accepted Submission(s): 1026
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
一道很好的拓撲排序題，因為有等號的緣故，所以加大了難度。
因為題目數據量比較大，所以肯定不能用鄰接矩陣來儲存關系，回超內存，所以果斷選擇用領接表表示，然後用了一下午的時間學習了STL裡面的vector
一開始沒有考慮到連等的情況，所以沒有用到並查集去合並‘=’而是純手動的度到‘=’就讓兩個點的入讀相等（這樣做完全行不通，不光出現1 = 2 = 3的情況回出錯，1 > 2, 2 = 3, 4 > 3 的時候也會WA）後來引入並查集去等以後就超時，經過很長時間的優化終於踩點過了，所以說有時候必要的學習時應該的。下面給出一些容易錯的數據（僅供參考）：
4 3
1 > 0
1 = 2
3 > 2
OK
5 4
1 > 0
1 = 2
2 = 3
3 < 4
OK
7 6
1 > 0
1 = 2
2 = 3
2 > 5
3 > 6
4 > 3
NUCERTAIN
我的解題思路：在讀如數據的同時， 碰到‘=’時用並查集進行處理，（這點不好，這樣由於‘=’的出現次序，數據要被重復合並多次），然後用模擬的方式去判斷（這裡沒有用到一些技巧很慚愧），因為名次時確定的話每次只會有一個點的入度為0，如果同時有兩個點的入度為0，說明名次不能被確定，如果有向圖中出現環，說明沖突。
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define N 10005
#define INT vector<int>::iterator
int n, m, cnt, all, bir[N];
int rec[N * 2][2], vis[N], num[N];
vector<int> G[N];
void handle(int a, int b){
if (a == b)
return;
for (INT i = G[a].begin(); i != G[a].end(); i++)
G[b].push_back(*i);
num[a] = b;
all++;
}
int find(int x){
return x != num[x]?num[x] = find(num[x]):x;
}
int topo(int k, int sum){
vis[k] = 1;
int ok = 0;
for (INT i = G[k].begin(); i != G[k].end(); i++){
int a = find(*i);
if (vis[a]) return -1;
ok = topo(a, sum + 1);
if (ok) return ok;
}
if (sum + all == n) return 1;
vis[k] = 0;
return 0;
}
int main(){
int a, b;
char c;
while (scanf("%d%d", &n, &m) != EOF){
// Init.
all = cnt = 0;
memset(rec, 0, sizeof(rec));
memset(bir, 0, sizeof(bir));
for (int i = 0; i < n; i++)
G[num[i] = i].clear();
// Read.
for (int i = 0; i < m; i++){
scanf("%d %c %d", &a, &c, &b);
if (c == '<')
G[b].push_back(a);
else if (c == '>')
G[a].push_back(b);
else{
rec[cnt][0] = a;
rec[cnt][1] = b;
cnt++;
}
}
// Handle.
for (int i = 0; i < cnt; i++)
handle(find(rec[i][0]), find(rec[i][1]));
// Judge.
int ok = 0;
for (int i = 0; i < n; i++){
a = find(i);
if (bir[a]) continue;
memset(vis, 0, sizeof(vis));
ok = topo(a, 1);
if (ok) break;
bir[a] = 1;
}
if (ok == 1)
printf("OK\n");
else if (ok == -1)
printf("CONFLICT\n");
else
printf("UNCERTAIN\n");
}
return 0;}
這是我研究了下別人的代碼，然後結合自己代碼優點寫的，主要改了數據讀入的地方，是在讀取到‘=’時，先用並查集將兩點合並（注意已經相等的點處理，對後面判斷回有所影響），在所有數據都讀取完畢後，在對‘<' 和‘>'進行處理（這裡處理時直接找到根結點，在根節點處操作）。
還有在拓撲排序的實現上引用了隊列進行模擬，起先處理時有記錄沒個點的入度個數，當入度為0時入隊，如果出現過隊列大小大於1的情況，說明排序不唯一，如果沒有點入度為0 時，被確定排序的點不足n個時，為沖突。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define N 10005
int n, m, cnt;
int X[2 * N], Y[2 * N], far[N], son[N];
char C[2 * N];
vector<int> G[N];
int get(int x){
return x != far[x]?far[x] = get(far[x]):x;
}
bool Union(int a, int b){
if (a == b)
return false;
far[a] = b;
return true;
}
int main(){
while (scanf("%d%d", &n, &m) != EOF){
// Init.
memset(son, 0, sizeof(son));
for (int i = 0; i < n; ++i)
G[far[i] = i].clear();
cnt = n;
// Read.
for (int i = 0; i < m; i++){
scanf("%d %c %d", &X[i], &C[i], &Y[i]);
if (C[i] == '=' && Union(get(X[i]), get(Y[i])))
cnt--;
}
// Handle.
for (int i = 0; i < m; i++){
int a = get(X[i]), b = get(Y[i]);
if (C[i] == '<'){
G[b].push_back(a);
son[a]++;
}
else if (C[i] == '>'){
G[a].push_back(b);
son[b]++;
}
}
queue<int> que;
int ok = 0;
for (int i = 0; i < n; i++)
if (!son[i] && i == get(i))
que.push(i);
while (!que.empty()){
if (que.size() > 1)
ok = 1;
int t = que.front();
que.pop();
cnt--;
for (int i = 0; i < G[t].size(); i++)
if (--son[G[t][i]] == 0)
que.push(G[t][i]);
}
if (cnt > 0)
printf("CONFLICT\n");
else if (ok)
printf("UNCERTAIN\n");
else
printf("OK\n");
}
return 0;}
