HDU 2652 / 福布斯排行榜：拓撲排序 + 並查集解題報告

題目大意

N 人按 Rating 降序、RP 降序（編號大 RP 高）排名。給 M 條關係（`>`, `=`, `<`），判斷能否唯一確定排名：
- 能唯一確定 → `OK`
- 信息不全（多種拓撲序） → `UNCERTAIN`
- 存在衝突（環） → `CONFLICT`（衝突優先）

解法：並查集 + 拓撲排序 (Kahn/BFS)

1. 並查集合並 `=` 關係：將等級相同的人合併為一個節點。
2. 建圖：`A > B` 表示 A→B 有向邊，入度++。
3. 拓撲排序：隊列存入度為 0 的節點。
   - 若某步隊列大小 > 1 → 存在多種拓撲序 → `UNCERTAIN`。
   - 若最終排序節點數 < 總節點數 → 有環 → `CONFLICT`。
   - 否則 → `OK`。

關鍵代碼片段

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

// 拓撲排序
queue q;
for (int i=1; i<=cnt; i++) if (indeg[i]==0) q.push(i);
bool uncertain = false;
int sorted = 0;
while (!q.empty()) {
    if (q.size() > 1) uncertain = true;
    int u = q.front(); q.pop();
    sorted++;
    for (int v : adj[u]) if (--indeg[v]==0) q.push(v);
}
if (sorted < cnt) return "CONFLICT";
return uncertain ? "UNCERTAIN" : "OK";

參考博客

shuangde800 詳細題解