关系链上的并查集

一、题目引入

最近做了一道很优美的使用并查集解决的问题：https://ac.nowcoder.com/acm/problem/16884 【2001NOI 食物链】

简要概括就是一共有A、B、C三种动物。A吃B，B吃C，C吃A。动物间有两种关系：

“1 X Y”，表示X和Y是同类
“2 X Y”，表示X吃Y。

现在给出k个关系，问这些关系中哪些是假的（与已有的关系冲突）

这是一道很经典的并查集问题，但是与一般的并查集题目不同的是，此题的集合可以选择构建一串逻辑自洽的关系链。

在解决这道题目之前，先来回顾一下两种基本的并查集操作：

合并：

1
2
3

void merge(int x, int y){
    pa[find(x)] = find(y);  //pa数组存储父亲节点
}

查询（+路径压缩）：

1
2
3

int find(int x){
    return pa[x] == x ? x : pa[x] = find(pa[x]); 
}

二、解题思路

此题可以用带权并查集解决，两点之间的距离代表着两者关系。经过三条边即一个A -> B -> C -> A的循环，相当于是属于同一个物种。不过本蒟蒻并不是很会带权并查集，一开始用这个方法一直没做对这道题（🍐）。后来看了题解发现一个让我眼前一亮的做法，遂记录在此。

正篇：

思路大意
- 将原先存储父亲节点的pa数组开三倍大。a[1]——a[n] 表示 i 为A动物的情况，a[n+1]——a[2n] 表示 i 为B动物的情况， a[2n+1]——a[3n] 表示 i 为C动物的情况。
  
  i 1 2 3 …… n
  
  A
  
  B
  
  C
  
  这样 i 对应的一竖列元素可以看作 i 号分别是A、B、C动物时的父亲节点（根节点的父亲就是自己）
- 由于有三个物种，第i个动物可能是A、B、C中任意一种（后续我们分别用iA，iB，iC表示）。在构建关系链的时候三种情况都要考虑，因此A、B、C都会延伸出一条链，一共三条链。若把多个竖列的三种情况都连接起来，那么这三条链记录着目前三种可能的关系链。每条关系链维护的是不同编号的动物之间的关系。
- 举例用“–”表示逻辑上相连，XA–YA，XB–YB，XC–YC代表X与Y属于同类。XA–YB，XB–YC，XC–YA代表X吃Y。
如何判断一个关系的正确性？
1. 输入是“1 X Y”
- 如果X和Y已经有关系了，那么XA肯定会与YA、YB或YC中的一个相连。
  （由于每次构建关系链的时候我们是三种情况（XA、XB、XC）都考虑的，因此只用考虑XA就行）
- 如果X和Y没有关系，则XA不会与YA、YB或YC中任意一个相连。这时候新输入的关系肯定是正确的
  假设现在输入“1 X Y”，我们会发现以XA和YA是否在一条链上作为判断依据，会导致第二种情况判断错误。因此我们从反面判断：如果XA与YB或YC相连，则新输入的关系是错误的。
1. 输入是“2 X Y”
- 同上，从反面考虑：如果XA与YA或YC相连，那么新输入的关系是错的，反之正确。
增添关系
- “1 X Y”：连XA与YA, XB与YB，XC与YC
- “2 X Y”：连XA与YB, XB与YC，XC与YA

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4;
vector <int> pa(3*N+10);   //记得开三倍大小的数组
//查询
int find(int x){
    return pa[x] == x ? x : pa[x] = find(pa[x]);
}
//合并
void merge(int x, int y){
    pa[find(x)] = find(y);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= 3 * n; i++){
        pa[i] = i;     //一开始无关系，都是根节点
    }
    int cnt = 0;
    for(int i = 1; i <= k; i++){
        int op, x, y;
        cin >> op >> x >> y;
        if(x > n || y > n){    //超出动物的编号，关系也是错误的
            cnt++;
            continue;
        }
        if(op == 1){    //"输入为1 X Y"
            //如果XA与YB或YC相连，则关系错误
            if(find(x) == find(y + n) || find(x) == find(y+2*n)){   
                cnt++;
            }else{     //否则在关系链上增添X与Y同类的关系
                merge(x, y);                    //连XA与YA
                merge(x + n, y + n);            //连XB与YB
                merge(x + 2 * n, y + 2 * n);    //连XC与YC
            }
        }else{    //"输入为2 X Y"
            //如果XA与YA或YC相连，则关系错误
            if(find(x) == find(y) || find(x) == find(y+2*n)){
                cnt++;
            }else{      //增添X捕食Y的关系
                merge(x, y + n);                //连XA与YB
                merge(x + n, y + 2*n);          //连XB与YC
                merge(x + 2 * n, y);            //连XC与YA
            }
        }
    }
    cout << cnt << '\n';
    return 0;
}

三、做题总结

经过此题的启发，我设想了一些推广，不过很多情况下不会有本题这么好的条件。此题之所以能用这种方法，是因为所有可能出现的关系都是基于A -> B -> C -> A的核心关系，并且种类个数是一个定值。而大多数并查集的题目种类数都不固定，因此这种方法泛用性较差。不过能想到这么做的人肯定是个天才👍

题外话

这是本蒟蒻第一次写完整的题解，若有不当还请谅解，之后争取不断进步。把思路记录下来主要还是便于自己回顾，部署到网站上是希望能够帮助一些一起学习的伙伴。（~~误人子弟了怎么办~~）

i	1	2	3	……	n
A
B
C