【算法基础篇】（二十四）数据结构之并查集拓展：从 “单一关系” 到 “复杂约束”，这篇带你解锁进阶玩法！

#include <iostream>
using namespace std;

const int N = 1010; // 假设最多1000人
int fa[N * 2]; // 扩展域：x是朋友域，x+N是敌人域
int n, m; // n是人数，m是关系数

// 初始化并查集（带路径压缩）
void init() {
    for (int i = 1; i <= 2 * n; i++) { // 注意：域的范围是1~2n
        fa[i] = i;
    }
}

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

void un(int x, int y) { // 合并x和y所在的集合
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fy] = fx; // 让y的根节点指向x的根节点（方向不影响，统一即可）
    }
}

// 处理关系：op是'F'（朋友）或'E'（敌人），x和y是两个人
void handle_relation(char op, int x, int y) {
    if (op == 'F') {
        // 朋友：x的朋友域 ↔ y的朋友域，x的敌人域 ↔ y的敌人域
        un(x, y);
        un(x + n, y + n);
    } else { // op == 'E'
        // 敌人：x的朋友域 ↔ y的敌人域，x的敌人域 ↔ y的朋友域
        un(x, y + n);
        un(x + n, y);
    }
}

bool is_friend(int x, int y) {
    return find(x) == find(y);
}

6
4
E 1 4
F 3 5
F 4 6
E 1 2

3

#include <iostream>
using namespace std;

const int N = 1010;
int fa[N * 2];
int n, m;

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

void un(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fy] = fx;
    }
}

int main() {
    cin >> n >> m;
    init(); // 初始化扩展域
    
    while (m--) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'F') {
            un(x, y);
            un(x + n, y + n);
        } else {
            un(x, y + n);
            un(x + n, y);
        }
    }
    
    // 统计独立的朋友域（根节点是自己的朋友域）
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i) { // 朋友域i的根是自己，说明是一个独立团伙
            cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

100 7
1 101 1 // X超范围，假话
2 1 2   // 真话
2 2 3   // 真话
2 3 3   // X吃X，假话
1 1 3   // 与1吃2、2吃3冲突，假话
2 3 1   // 真话（3是C，1是A，C吃A）
1 5 5   // 真话

3

#include <iostream>
using namespace std;

const int N = 5e4 + 10; // 最多5e4个动物
int fa[N * 3]; // 3个域：x（同类）、x+N（捕食）、x+2N（被捕食）
int n, k;

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

void un(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fy] = fx;
    }
}

int main() {
    cin >> n >> k;
    // 初始化3个域
    for (int i = 1; i <= 3 * n; i++) {
        fa[i] = i;
    }
    
    int lie = 0; // 假话数量
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        
        // 假话条件1：X或Y超范围
        if (x > n || y > n) {
            lie++;
            continue;
        }
        
        // 假话条件2：X吃X（op=2且x=y）
        if (op == 2 && x == y) {
            lie++;
            continue;
        }
        
        if (op == 1) { // X和Y是同类
            // 冲突判断：X的捕食域包含Y，或X的被捕食域包含Y
            if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) {
                lie++;
            } else {
                // 合并同类、捕食、被捕食域
                un(x, y);
                un(x + n, y + n);
                un(x + 2 * n, y + 2 * n);
            }
        } else { // op=2，X吃Y
            // 冲突判断：X和Y是同类，或X的被捕食域包含Y（Y吃X）
            if (find(x) == find(y) || find(x) == find(y + n)) {
                lie++;
            } else {
                // 合并：X捕食Y同类，X同类是Y被捕食，X被捕食是Y捕食
                un(x + n, y);
                un(x, y + 2 * n);
                un(x + 2 * n, y + n);
            }
        }
    }
    
    cout << lie << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int fa[N];   // 父节点数组
int d[N];    // 权值数组：d[x]表示x到fa[x]的距离
int n;       // 节点总数

void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        d[i] = 0; // 自己到自己的距离为0
    }
}

int find(int x) {
    if (fa[x] == x) { // 找到根节点，直接返回
        return x;
    }
    // 先递归找到根节点（必须先找根，再更新父节点和权值）
    int root = find(fa[x]);
    // 更新权值：x到根的距离 = x到原父节点的距离 + 原父节点到根的距离
    d[x] += d[fa[x]];
    // 路径压缩：x的父节点直接指向根
    fa[x] = root;
    return root;
}

// 合并x和y所在的集合，且x到y的距离为w
void un(int x, int y, int w) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fx] = fy; // 让fx的父节点指向fy
        // 推导：x到y的距离 = x到fx的距离 + fx到fy的距离 - y到fy的距离
        // 即 w = d[x] + d[fx] - d[y] → d[fx] = d[y] + w - d[x]
        d[fx] = d[y] + w - d[x];
    }
}

const int INF = 0x3f3f3f3f;
// 查询x到y的距离，不在同一集合返回INF
int query(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        return INF;
    }
    return d[x] - d[y];
}

#include <iostream>
using namespace std;

const int N = 5e4 + 10;
int fa[N];
int d[N]; // d[x]表示x到根节点的种类差，d[x]%3表示关系
int n, k;

int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    int root = find(fa[x]);
    d[x] += d[fa[x]]; // 更新x到根的种类差
    fa[x] = root;
    return root;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        d[i] = 0;
    }
    
    int lie = 0;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        
        if (x > n || y > n) { // 超范围
            lie++;
            continue;
        }
        if (op == 2 && x == y) { // X吃X
            lie++;
            continue;
        }
        
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) { // 已在同一集合，判断是否冲突
            if (op == 1) {
                // 同类：(d[y]-d[x])%3应等于0
                if ((d[y] - d[x]) % 3 != 0) {
                    lie++;
                }
            } else { // op==2，X吃Y：(d[y]-d[x])%3应等于1
                if ((d[y] - d[x]) % 3 != 1) {
                    lie++;
                }
            }
        } else { // 未合并，执行合并
            if (op == 1) {
                // X和Y是同类，x到y的距离为0 → w=0
                un(x, y, 0);
            } else {
                // X吃Y，x到y的距离为1 → w=1
                un(x, y, 1);
            }
        }
    }
    
    cout << lie << endl;
    return 0;
}

4
M 2 3 // 2的队列接在3后面：3 → 2
C 1 2 // 1和2不在同一列，输出-1
M 2 4 // 2的队列（3→2）接在4后面：4 → 3 → 2
C 4 2 // 4和2之间有1艘战舰（3），输出1

-1
1

#include <iostream>
#include <cmath>
using namespace std;

const int N = 3e4 + 10;
int fa[N];   // 父节点
int d[N];    // d[x]：x到根节点的距离（前面有多少艘战舰）
int cnt[N];  // cnt[x]：根节点x的队列大小
int n = 3e4; // 固定30000列

int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    int root = find(fa[x]);
    d[x] += d[fa[x]]; // 更新x到根的距离
    fa[x] = root;
    return root;
}

// 合并i和j的队列：i的队列接在j的队列后面
void un(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
        d[fx] = cnt[fy]; // fx队列头部到fy队列尾部的距离是fy的队列大小
        cnt[fy] += cnt[fx]; // 更新fy的队列大小
    }
}

// 查询x和y之间的战舰数
int query(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        return -1;
    }
    return abs(d[x] - d[y]) - 1; // 距离差减1是中间的战舰数
}

int main() {
    // 初始化：每个战舰自己是一个队列
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        d[i] = 0;
        cnt[i] = 1; // 初始队列大小为1
    }
    
    int T;
    cin >> T;
    while (T--) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'M') {
            un(x, y);
        } else {
            cout << query(x, y) << endl;
        }
    }
    
    return 0;
}