HDU 1811 Rank of Tetris：拓撲排序與並查集判斷關係

問題描述

給定 n 個積木塊，m 條關係（<, >, =），判斷關係是否自洽：

• OK：存在唯一拓撲序。
• CONFLICT：存在矛盾（環）。
• UNCERTAIN：多種拓撲序（某時刻隊列中有多個入度為 0 的節點）。

解題策略

1. 並查集合併「=」關係：將相等的塊合併為同一集合，視為同一節點。
2. 建立有向圖：針對 < 和 > 關係，在集合代表元之間加有向邊，統計入度。
3. Kahn 拓撲排序：隊列維護入度為 0 的節點。若某步隊列大小 > 1，標記 UNCERTAIN。若最終處理節點數 < 總集合數，存在環 → CONFLICT。否則 OK。

關鍵代碼邏輯

// 並查集
int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int a, int b) { a=find(a); b=find(b); if(a!=b) fa[a]=b; }

// 處理 "=" 合併
for each relation: if(op=="=") unite(x,y);

// 建圖
for each relation:
    int u=find(x), v=find(y);
    if(op==">") addEdge(u,v), indeg[v]++;
    if(op=="<") addEdge(v,u), indeg[u]++;

// 拓撲
queue q;
for i in 0..n-1 if(i==find(i) && indeg[i]==0) q.push(i);
bool uncertain = false;
int processed = 0;
while(!q.empty()) {
    if(q.size() > 1) uncertain = true;
    int u = q.front(); q.pop();
    processed++;
    for v in adj[u] if(--indeg[v]==0) q.push(v);
}
if(processed < total_sets) CONFLICT;
else if(uncertain) UNCERTAIN;
else OK;

複雜度與細節

• 時間 O(n + m α(n))，空間 O(n + m)。
• 注意：合併後節點數變少，入度統計、建圖均以代表元為準。
• 題目保證無自環、重邊，但合併後可能出現自環（如 a>b, b=a），建圖時可檢測 u==v 直接判衝突。