Codeforces 216B Forming Teams：並查集處理敵對關係分組

題目

n 人，m 對敵對關係（每人敵人 ≤ 2）。需分成兩隊人數相等，敵對者不在同隊。求最少淘汰人數。

圖論建模

• 敵對關係構成無向圖，度數 ≤ 2 → 圖由鏈和環組成。
• 二分圖著色：若連通塊為奇環，無法二分，需移除至少 1 人打破奇環。
• 並查集維護「同隊」關係，enemy[x] 記錄 x 的敵人代表元。

並查集合併邏輯

處理邊 (x,y)：

x = find(x); y = find(y);
if (x == y) { ans++; continue; } // 同組發現衝突，需移除一人
if (!enemy[x] && !enemy[y]) { enemy[x]=y; enemy[y]=x; }
else if (!enemy[x]) { enemy[x]=y; unite(x, enemy[y]); }
else if (!enemy[y]) { enemy[y]=x; unite(enemy[x], y); }
else { unite(enemy[x], y); unite(x, enemy[y]); }

最終調整

統計衝突數 ans（奇環導致的移除）。剩餘 n - ans 人若為奇數，再淘汰 1 人使兩隊均分。輸出 ans + (n-ans)%2。

完整 C++ 代碼

#include 
using namespace std;
const int MAXN = 105;
int fa[MAXN], enemy[MAXN];
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); }

int main() {
    int n,m;
    while(cin>>n>>m){
        iota(fa, fa+n+1, 0);
        fill(enemy, enemy+n+1, 0);
        int ans=0;
        for(int i=0;i>x>>y;
            x=find(x); y=find(y);
            if(x==y) ans++;
            else if(!enemy[x]&&!enemy[y]) enemy[x]=y, enemy[y]=x;
            else if(!enemy[x]) enemy[x]=y, unite(x,enemy[y]);
            else if(!enemy[y]) enemy[y]=x, unite(enemy[x],y);
            else unite(enemy[x],y), unite(x,enemy[y]);
        }
        if((n-ans)%2) ans++;
        cout<