食物鏈問題是「並查集維護模 3 關係」的經典應用。本文從問題建模、三倍擴展域構造、關係合併邏輯、路徑壓縮下的關係更新、完整 C++ 實現、錯誤判定規則六個維度，徹底攻克此類帶權并查集問題。
N 隻動物，編號 1..NA,B,C，循環捕食 A→B→C→AK 條，兩類：
1 x y：x 與 y 同類2 x y：x 吃 yx 或 y 超出 [1,N]2 x x：自己吃自己為每隻動物 x 創建三個節點：
x：代表「x 是 A 類」x + N：代表「x 是 B 類」x + 2N：代表「x 是 C 類」並查集大小：3N + 1（1-based 索引）。
| 語句 | 邏輯含義 | 合併操作 |
|---|---|---|
1 x y (同類) | x 類 = y 類 | union(x, y); union(x+N, y+N); union(x+2N, y+2N) |
2 x y (x吃y) | x 類 = y 類的捕食者 | union(x, y+N); union(x+N, y+2N); union(x+2N, y) |
捕食循環：A→B, B→C, C→A 對應索引偏移 +N, +N, -2N (≡ +N mod 3N)。
// 1 x y (同類)
if (find(x) == find(y+N) || find(x) == find(y+2N)) // x 與 y 的其他類同類 → 矛盾
return false;
// 2 x y (x吃y)
if (find(x) == find(y) || find(x) == find(y+2N)) // x 與 y 同類 或 x 被 y 吃 → 矛盾
return false;
#include <stdio.h>
#include <string.h>
#define MAX_N 50000
#define MAX_K 100000
int N, K;
int parent[MAX_N * 3 + 1];
int rank_[MAX_N * 3 + 1];
void init(int n) {
for (int i = 1; i <= 3*n; i++) {
parent[i] = i;
rank_[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路徑壓縮
}
return parent[x];
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rank_[x] < rank_[y]) {
parent[x] = y;
} else {
parent[y] = x;
if (rank_[x] == rank_[y]) rank_[x]++;
}
}
bool same(int x, int y) {
return find(x) == find(y);
}
int main() {
scanf("%d %d", &N, &K);
init(N);
int errors = 0;
for (int i = 0; i < K; i++) {
int D, X, Y;
scanf("%d %d %d", &D, &X, &Y);
if (X < 1 || X > N || Y < 1 || Y > N) {
errors++; continue;
}
if (D == 1) { // 同類
if (same(X, Y+N) || same(X, Y+2N)) {
errors++;
} else {
unite(X, Y);
unite(X+N, Y+N);
unite(X+2N, Y+2N);
}
} else { // D==2, X吃Y
if (X == Y || same(X, Y) || same(X, Y+2N)) {
errors++;
} else {
unite(X, Y+N);
unite(X+N, Y+2N);
unite(X+2N, Y);
}
}
}
printf("%d\n", errors);
return 0;
}
輸入: 100 7 1 101 1 # 錯誤: 101 > N 2 1 2 # 1吃2 2 2 3 # 2吃3 2 3 3 # 錯誤: 自己吃自己 1 1 3 # 錯誤: 1與3同類, 但1吃2吃3推導1吃3 2 3 1 # 3吃1 (合法, 形成循環) 1 5 5 # 5與5同類 (合法) 輸出: 3
標準並查集路徑壓縮 parent[x] = find(parent[x]) 僅改變父指針，不改變 x 所在的等價類。由於我們將「同類/捕食」關係編碼為同一等價類（通過三倍域映射），路徑壓縮天然保持關係正確性，無需額外維護權重/距離。
| 變體 | 修改點 | 應用 |
|---|---|---|
| 模 4 關係 | 四倍域，偏移 +N/+2N/+3N | 四態循環關係 |
| 帶權重並查集 | 維護 dist[x] 到根距離，模運算 | 模塊化方程組、電位差 |
| 動態加點 | 初始化父指針指向自身 | 在線算法 |
| 撤銷操作 | 可持久化並查集 / 分治 + 回滾 | 離線動態連通性 |
O(K α(3N)) ≈ O(K)，α 為反阿克曼函數，極慢增長O(N)（三倍常數因子）3*N+1，別寫成 3*N 導致越界y+N、y+2N 而非 y+1、y+2D==2 && X==Y 直接判錯，勿進合併邏輯X<1 || X>N || Y<1 || Y>N 優先判斷食物鏈問題展示了「領域建模」的威力：將複雜的邏輯關係（同類、捕食、被捕食）映射為並查集中的等價類合併，將矛盾檢測簡化為「同一集合」判斷。三倍擴展域技巧同樣適用於「三色圖著色」「模 3 線性方程組」「石頭剪刀布循環博弈」等問題。建議在紙上手推樣例的合併過程，親眼見證等價類如何演化。
