并查集提高——種類并查集（反集）

前言：

本蒟蒻在今天刷題時遇到了種類并查集的問題，遂決定，花1小時學學，并寫篇文章記錄一下；
那么如果你認真讀完本文，你將自己發(fā)明種類并查集（反集）；
前置知識：普通并查集；

引子題： P1892 [BalticOI 2003] 團伙

## 題目描述
現(xiàn)在有 \(n\) 個人，他們之間有兩種關系：朋友和敵人。我們知道：

一個人的朋友的朋友是朋友
一個人的敵人的敵人是朋友

現(xiàn)在要對這些人進行組團。兩個人在一個團體內當且僅當這兩個人是朋友。請求出這些人中最多可能有的團體數(shù)。

## 輸入格式
第一行輸入一個整數(shù) \(n\) 代表人數(shù)。
第二行輸入一個整數(shù) \(m\) 表示接下來要列出 \(m\) 個關系。
接下來 \(m\) 行，每行一個字符 \(opt\) 和兩個整數(shù) \(p,q\)，分別代表關系（朋友或敵人），有關系的兩個人之中的第一個人和第二個人。其中 \(opt\) 有兩種可能：

如果 \(opt\) 為 `F`，則表明 \(p\) 和 \(q\) 是朋友。
如果 \(opt\) 為 `E`，則表明 \(p\) 和 \(q\) 是敵人。

## 輸出格式
一行一個整數(shù)代表最多的團體數(shù)。

## 說明/提示
對于 \(100\%\) 的數(shù)據(jù)，\(2 \le n \le 1000\)，\(1 \le m \le 5000\)，\(1 \le p,q \le n\)。

解法：

上面的題在洛谷，可以自己嘗試；

如果你沒學過種類并查集（反集），你應該會想到使用并查集維護朋友關系，用數(shù)組維護敵人關系，隨后遍歷每個人的每個敵人的每個敵人，將這個人和他敵人的敵人合并；
但是，我們注意到，這樣做的代價是：空間復雜度 \(O(n^2)\) ，時間復雜度 \(O(n^3)\) ；
若是題目的數(shù)據(jù)再大一個數(shù)量級，這么做會爆；
不過，這樣也可以AC了這道題，畢竟還是比較水的；

如果你想到了維護敵人并查集，那你已經(jīng)有了相當好的直覺，事實上，種類并查集也類似在維護一個新并查集；
但是，對于敵人并查集，這里的設定很關鍵：如果你設成一個集合內部是朋友，那么會非常復雜，問題是，你如何由敵對推出朋友呢，仍然需要存儲每個人的敵人，這樣做依然不好；
如果你設定一個集合內部是敵人，那么一個人和另一個人的關系仍然不好維護，因為如果是朋友關系，AB是朋友，BC是朋友，AC一定是朋友，但是對于敵對關系，AB是敵人，BC是敵人，AC就是朋友了；
這破壞了集合傳遞性（即若AB共集，BC共集，那么AC共集）；

我們先來反思一下為什么普通并查集不行：
最重要的是，敵人關系不滿足集合的傳遞性這個數(shù)學要求，從而并查集不成立；
事實上，普通并查集維護的是兩個人是不是共集的信息，而對于兩個人各自的相對身份（注意：相對身份，A對于B是朋友，對于C可能就是敵人了）我們一無所知；
那么怎樣維護這種多重身份呢；（換言之，怎樣恢復傳遞性）

從傳遞性入手：朋友關系才具有傳遞性，所以我們要想辦法將敵對關系換成朋友關系；
“敵人關系本身不傳遞，但敵人的敵人是朋友——這句話其實把‘敵對’轉換成了‘朋友’，于是我們又可以用并查集了。”

若是我們開一個長度為 \(2n\) 的并查集
1.當 \(1 \le i \le n\) 時，i為其朋友集，所有與i是朋友關系的人會接到這個集合中（即普通的并查集）
2.當 \(n+1 \le i \le 2n\) 時，i(實際上是i+n)為敵對集，所有i的敵人都會接入這個集合中

若 \(u,v\) 是朋友，我們執(zhí)行 union_set(u,v)，若 \(u,v\) 是敵人，我們 union_set(u+n,v) 、union_set(u,v+n);
朋友顯然不需要解釋，那么敵人為什么要這樣合并呢，我們依據(jù)定義：所有i的敵人是i的敵對集的成員，那么誰和u的敵人共集呢，顯然也是u的敵人，所以有了：union_set(u+n,v)，即將v加入u的敵人集；
那么誰和u共集呢，顯然是v的敵人，所以有union_set(u,v+n)；
這樣實際上利用了：敵人的敵人就是朋友這一性質，將無法維護（無法合并）的敵對關系換成了朋友關系；

接下來思考這樣一個問題：若一個人同時是兩個人的敵人，沖突嗎；
你可能會覺得，這會沖突，因為根據(jù)集合的定義，不允許一個人同時歸屬兩個集合，但是注意，我們使用的是并查集，這兩個集合會合并，因此并不沖突；

以下為題解：

WriteUp 種類并查集解
我們定義，在 \(f_i\) 中，當 \(1 \le i \le n\) 時，為i的朋友集，當 \(n+1 \le i+n \le 2n\) 時，為i的敵對集；
當 \(u,v\) 是朋友，我們執(zhí)行 union_set(u,v)，當 \(u,v\) 是敵人，我們 union_set(u+n,v) 、union_set(u,v+n);
下面給出AC代碼：

#include<iostream>
using namespace std;
int n, m;
char x;      // 操作符
int fa[2006]; // 并查集數(shù)組，大小設為2*n
int t1, t2;  
int ans;
bool vis[2006]; // 用于標記已統(tǒng)計的根節(jié)點

int findx(int x) {
    return x == fa[x] ? x : fa[x] = findx(fa[x]);
}

void union_set(int x, int y) {
    int rx = findx(x), ry = findx(y);
    if (rx != ry) {
        fa[rx] = ry;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> x;
        if (x == 'F') {
            cin >> t1 >> t2;
            union_set(t1, t2);
        } else {
            cin >> t1 >> t2;
            union_set(t1 + n, t2);
            union_set(t1, t2 + n);
        }
    }
    // 路徑壓縮所有主要節(jié)點
    for (int i = 1; i <= n; i++) {
        findx(i);
    }
    // 統(tǒng)計不同根節(jié)點
    for (int i = 1; i <= n; i++) {
        int root = findx(i);
        if (!vis[root]) {
            vis[root] = true;  //統(tǒng)計所有不一樣的根，因為可能有的以敵人集為根
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

具體的運作流程：

我們先定義這樣一些關系，方便演示：
1 2 是朋友，1 3 是朋友
1 4 是敵人，4 5 是敵人；

根據(jù)我們的定義，最終，1235是一個集合
接下來看圖：
我們先加入朋友邊，不難發(fā)現(xiàn)，1 2 3形成了一個聯(lián)通的區(qū)域，我們稱為一個聯(lián)通塊，顯然，同一個聯(lián)通塊是一個集合；
截屏2025-08-28 09.56.03

隨后，加入（1，4反集），（1反集，4）這兩個敵人邊，即（1，9）（6，4），這里n=5，一共五個人；
現(xiàn)在出現(xiàn)了兩個聯(lián)通塊，分別是：（1，2，3，4反），（4，1反）；
截屏2025-08-27 11.37.29

我們繼續(xù)加入4，5的敵人關系，就是：（4，5反）（4反，5），即（4，10）（9，5）；
截屏2025-08-27 11.33.59

不難發(fā)現(xiàn)，現(xiàn)在，并查集已經(jīng)正確處理了所有的關系；
更準確的說，4的反集是一個中間量，建立起了1和5的朋友關系（由于4的敵人和1是一個集，所以1，5共集），這就是反集的作用，它通過轉換，維護了不具備傳遞性的敵人關系；

這里有個坑，不難發(fā)現(xiàn)，我在代碼中使用了vis數(shù)組，這是由于敵人集可能是根，也需要一并統(tǒng)計；

例題2:P2024 [NOI2001] 食物鏈

## 題目描述

動物王國中有三類動物 \(A,B,C\)，這三類動物的食物鏈構成了有趣的環(huán)形。\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。
現(xiàn)有 \(N\) 個動物，以 \(1 \sim N\) 編號。每個動物都是 \(A,B,C\) 中的一種，但是我們并不知道它到底是哪一種。
有人用兩種說法對這 \(N\) 個動物所構成的食物鏈關系進行描述：

第一種說法是 `1 X Y`，表示 \(X\) 和 \(Y\) 是同類。
第二種說法是`2 X Y`，表示 \(X\) 吃 \(Y\)。

此人對 \(N\) 個動物，用上述兩種說法，一句接一句地說出 \(K\) 句話，這 \(K\) 句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

當前的話與前面的某些真的話沖突，就是假話；
當前的話中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假話；
當前的話表示 \(X\) 吃 \(X\)，就是假話。

你的任務是根據(jù)給定的 \(N\) 和 \(K\) 句話，輸出假話的總數(shù)。

## 輸入格式

第一行兩個整數(shù)，\(N,K\)，表示有 \(N\) 個動物，\(K\) 句話。
第二行開始每行一句話（按照題目要求，見樣例）

## 輸出格式
一行，一個整數(shù)，表示假話的總數(shù)。

WriteUp：

這道題我們可以通過擴展并查集（種類并查集）來做，也可以使用加權并查集；
當然，由于還沒講到加權并查集，這里使用擴展并查集；
補充一個點：有幾種關系就要開幾倍的并查集；

接下來分析一下這道題：
一共三種動物，A吃B，B吃C，C吃A，所以我們開 \(3 \times n\) 的種類并查集；
那么一共兩種情況（我們先假設都為真）：1. \(X\) 和 \(Y\) 是同類，2. \(X\) 吃 \(Y\) ；
細分下去，當 \(X\) 和 \(Y\) 是同類時，我們其實不知道 \(X\) 和 \(Y\) 具體屬于AA、BB還是CC，因此，我們需要合并3個集合中的XY，這代表XY是同類
同樣，當 \(X\) 吃 \(Y\) 時，我們也不知道是AB、BC還是AC，同樣需要合并x的A集和y的B集、x的B集和y的C集、x的C集和y的A集；

上面的分類不好理解，更準確的講，我們稱A集為本體集，B集為獵物集，C集為天敵集

對于同類，同類的天敵就是天敵，同類的獵物就是獵物
對于y是x的獵物，將y加入x的獵物集，將x加入y的天敵集，將x的天敵加入y的獵物集
（這里只有“將x的天敵加入y的獵物集”是不好理解的，我們進行一下推理：設z是x的天敵，由于y是x的獵物，x是z的獵物，那么z是y的獵物（因為C吃A））

那么，怎樣判斷一句話是否為假呢？
題目給了我們提示：

當前的話與前面的某些真的話沖突，就是假話；
當前的話中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假話；
當前的話表示 \(X\) 吃 \(X\)，就是假話。

后兩個比較好判斷，關鍵是1，什么叫沖突；

根據(jù)真假逆命題的關系，我們反轉條件，歸結為下面的幾類：
1.xy是同類，但是當前的話表示：x吃y或者y吃x；
2.x吃y，但是當前的話表示：y吃x、xy是同類

下面給出AC代碼：

#include<cstdio>
using namespace std;
int n,k;
int op,p,q;
int ans;
int fa[150004];
int findx(int x) {
    return x==fa[x]?x:fa[x] = findx(fa[x]);
}
void union_set(int u,int v) {
    int rx = findx(u),ry = findx(v);
    if (rx!=ry) {
        fa[ry] = rx;
    }
}
void init(int x) {
    for (int  i=1;i<=x;i++) {
        fa[i] = i;
    }
}
bool is_not_lie(int o,int x,int y) {
    if (x>n || y>n) return false; //xy比n大
    if (o==1) {
        if (findx(x)==findx(y+n)||findx(y)==findx(x+n)) {
            //x是y的獵物，或者y是x的獵物
            return false;
        }
    }else {
        if (x==y) return false;//x吃x
        if (findx(x)==findx(y+n)) return false; //x是y的獵物
        if (findx(x)==findx(y)) return false; //是同類
    }
    return true;
}
int main() {
    scanf("%d %d",&n,&k);
    init(3*n);
    for(int i=1;i<=k;i++) {
        scanf("%d %d %d",&op,&p,&q);
        if (!is_not_lie(op,p,q)) {
            ans++;
            continue;
        }else {
            if (op==1) {
                union_set(p,q);// 同類
                union_set(p+n,q+n);// 同類的獵物是獵物
                union_set(p+2*n,q+2*n); // 同類的敵人是敵人
            }else {
                union_set(p+n,q); //y是x的獵物
                union_set(p,q+2*n);//x是y的天敵
                union_set(p+2*n,q+n);//由 y->x->z->y 得x的天敵是y的獵物
            }
        }
    }
    printf("%d",ans);
    return 0;
}

補充：

1.對于第一題，普通做法是 \(O(n^3)\) 的，種類并查集做法是 \(O(n \alpha(a))\) 的，近似線性；
2.對于并查集的題目，可以采用先不編寫函數(shù)實現(xiàn)，直接寫main，之后依次實現(xiàn)需要的函數(shù)和變量的方法；
3.種類并查集是加權并查集的特例，這里面的兩道題都可以使用加權并查集做，但是邏輯比較復雜，空間會更?。ㄈ詾槠胀ú⒉榧拇笮。?\(O(n)\) ）

結語：

“當你在鍛煉，你覺得自己很累時，實際上你在變強；當你在學習，你覺得自己很傻時，其實你在變聰明”

所以，不要放棄嘗試困難的東西，那些NOI隨便就AK的人，也是這么過來的

如有筆誤，煩請諸位不吝賜教；

Upt 2025.8.27

posted @ 2025-08-27 22:01 Ghost-Face 閱讀(184) 評論(0) 收藏舉報

刷新頁面返回頂部

GhostFace的Blogs