POJ 1417 True Liars：並查集與動態規劃判斷部落身份

問題建模

p1 個神族（真話），p2 個魔族（謊話）。n 條陳述「x 說 y 是神族/魔族」。無矛盾數據，判斷能否唯一確定所有神族成員。

並查集維護關係

• 「x 說 y 是神族」→ x、y 同類；「x 說 y 是魔族」→ x、y 異類。
• 並查集節點存儲：num[root][0] 與根同類人數，num[root][1] 異類人數。
• 合併時根據關係翻轉計數：同類合併直接相加，異類合併交換 0/1 後相加。

動態規劃求可行分配

設 dp[i][j] 前 i 個集合恰有 j 個神族的方案數。轉移：

dp[i][j] += dp[i-1][j - num[root][0]]  // 根為神族
dp[i][j] += dp[i-1][j - num[root][1]]  // 根為魔族

若 dp[total][p1] == 1 唯一解，回溯確定每個集合根的身份，再 DFS 恢復具體成員。

關鍵代碼結構

struct Node { int v, w, next; } edge[10005]; // 圖存儲同/異關係
void dfs1(int u, int k) { // 預處理 ok[u][v] 同類標記
    tmp[u] = k;
    for (int i=pp[u]; i; i=edge[i].next) {
        int v = edge[i].v;
        if (!vis[v]) { vis[v]=1; dfs1(v, k^(!edge[i].w)); }
    }
}
void Merge(int x, int y) { // 並查集合併，根據 ok[x][y] 更新 num[][0/1] }
void solve() { // DP + 回溯輸出
    // dp[cnt][p1] == 1 時回溯 path[][] 確定每集合根身份
    // dfs(根, 1, 目標身份) 收集所有神族編號，排序輸出
}

複雜度

並查集近似 O(α(n))，DP 狀態 O((p1+p2) * p1) ≤ 600*300，完全可行。