struct DSU {
    vector<int> pa, sz;   // sz[i] = i 为根时，这棵树的节点总数
    int groups;           // 当前连通块数量
    
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);  // pa[i] = i
    }
    
    // 路径压缩查根
    int find(int x) {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }
    
    // 按节点数合并，返回 true 表示两者原本不连通（发生了合并）
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;       // 已在同一集合
        if (sz[x] < sz[y]) swap(x, y); // x 是大树
        pa[y] = x;                      // 小树接到大树
        sz[x] += sz[y];
        groups--;
        return true;
    }
    
    // 判断是否连通
    bool connected(int x, int y) { return find(x) == find(y); }
    
    // 所在连通块大小
    int size(int x) { return sz[find(x)]; }
};

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    int groups;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y]; groups--;
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    
    while (q--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            // 建立链路
            if (dsu.unite(a, b))
                cout << "新增链路：" << a << " - " << b << "\n";
            else
                cout << "已连通，无需新增\n";
        } else {
            // 查询
            cout << (dsu.connected(a, b) ? "可以通信" : "无法通信") << "\n";
        }
    }
    return 0;
}

我们有：dist[x] = height[x] - height[rx]
        dist[y] = height[y] - height[ry]

若把 ry 接到 rx 下，则需要 dist[ry] 满足：
    height[ry] - height[rx] = ?
    
由 height[y] - height[x] = d 推导：
    (dist[y] + height[ry]) - (dist[x] + height[rx]) = d
    height[ry] - height[rx] = d + dist[x] - dist[y]

所以 dist[ry] = d + dist[x] - dist[y]

// 完整带权并查集
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int pa[MAXN], sz[MAXN];
long long dist[MAXN];  // dist[x] = height[x] - height[find(x)]

void init(int n) {
    for (int i = 1; i <= n; i++) { pa[i] = i; sz[i] = 1; dist[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    dist[x] += dist[pa[x]];
    pa[x] = root;
    return root;
}

// 声明 height[y] - height[x] = d
// 返回 true = 无矛盾；false = 与已知矛盾
bool unite(int x, int y, long long d) {
    int rx = find(x), ry = find(y);
    long long dx = dist[x], dy = dist[y];
    
    if (rx == ry) {
        // 已在同集合，验证是否矛盾
        return (dy - dx == d);
    }
    
    // 合并：小树接大树
    if (sz[rx] < sz[ry]) {
        swap(rx, ry); swap(dx, dy); d = -d;
    }
    pa[ry] = rx;
    dist[ry] = d + dx - dy;
    sz[rx] += sz[ry];
    return true;
}

long long query(int x, int y) {
    find(x); find(y);
    return dist[y] - dist[x];  // height[y] - height[x]
}

int main() {
    int n = 5;
    init(n);
    
    unite(1, 2, 3);   // height[2] - height[1] = 3（2 比 1 高 3cm）
    unite(2, 3, 5);   // height[3] - height[2] = 5
    
    // 查询 1 和 3 的差
    cout << "3 比 1 高 " << query(1, 3) << " cm\n";  // 输出 8
    
    // 添加矛盾信息
    cout << (unite(1, 3, 10) ? "一致" : "矛盾") << "\n";  // 矛盾（应该是8）
    cout << (unite(1, 3, 8)  ? "一致" : "矛盾") << "\n";  // 一致
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;
int pa[MAXN * 3], sz[MAXN * 3];

void init(int n) {
    for (int i = 0; i < 3 * (n + 1); i++) { pa[i] = i; sz[i] = 1; }
}
int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    pa[y] = x; sz[x] += sz[y];
}

int main() {
    int n, k;
    cin >> n >> k;
    init(n);
    
    int lies = 0;
    while (k--) {
        int t, x, y;
        cin >> t >> x >> y;
        
        // 编号越界直接判假
        if (x < 1 || x > n || y < 1 || y > n) { lies++; continue; }
        
        if (t == 1) {
            // 声明 x 和 y 同类
            if (same(x, y + n) || same(x, y + 2 * n)) {
                lies++;  // 矛盾：x 和 y 之间有捕食关系
            } else {
                unite(x, y);
                unite(x + n, y + n);
                unite(x + 2 * n, y + 2 * n);
            }
        } else {
            // 声明 x 吃 y
            if (x == y) { lies++; continue; }  // 自己不能吃自己
            if (same(x, y) || same(x, y + n)) {
                lies++;  // 矛盾
            } else {
                unite(x + n, y);
                unite(x + 2 * n, y + n);
                unite(x, y + 2 * n);
            }
        }
    }
    
    cout << lies << "\n";
    return 0;
}

思路： 每次合并时若两人原本不在同一集合（unite 返回 true），连通块数 -1。最终 dsu.groups 就是答案。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    int groups;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y]; groups--;
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int a, b; cin >> a >> b;
        dsu.unite(a, b);
    }
    cout << dsu.groups << "\n";
    return 0;
}

追踪（N=5, M=3）：

初始 groups = 5
unite(1,2) → 不同集合，groups = 4，pa[2]=1
unite(2,3) → 不同集合，groups = 3，pa[3]=1
unite(4,5) → 不同集合，groups = 2，pa[5]=4
输出：2 ✓

思路： 加一条边 (u, v) 时，若 u 和 v 已经连通（find(u)==find(v)），则这条边构成环。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;  // 已连通 = 加边后形成环
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    bool has_cycle = false;
    while (m--) {
        int u, v; cin >> u >> v;
        if (!dsu.unite(u, v)) has_cycle = true;
    }
    cout << (has_cycle ? "YES" : "NO") << "\n";
    return 0;
}

关键点： unite 返回 false 代表两端已连通 → 这条边是多余边 → 存在环。

思路： 用带 sz[] 的并查集，合并结束后遍历所有节点，找 sz[find(i)] 的最大值。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
    }
    int size(int x) { return sz[find(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int u, v; cin >> u >> v;
        dsu.unite(u, v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dsu.size(i));
    cout << ans << "\n";
    return 0;
}

思路： Kruskal 算法：将所有边按权重从小到大排序，依次尝试加入。若两端不在同一集合（不会成环），则加入 MST。最终若 MST 边数 = N-1，则图连通。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());  // 按权重排序
    
    DSU dsu(n);
    long long total = 0;
    int cnt = 0;  // MST 中的边数
    
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            total += w;
            cnt++;
            if (cnt == n - 1) break;  // 找够 n-1 条边
        }
    }
    
    cout << (cnt == n - 1 ? total : -1) << "\n";
    return 0;
}

追踪示例（N=4, 边：1-2权1, 2-3权2, 1-3权3, 3-4权4）：

排序后：(1,1,2), (2,2,3), (3,1,3), (4,3,4)

加边(1,2)权1 → unite成功，cnt=1，total=1
加边(2,3)权2 → unite成功，cnt=2，total=3
加边(1,3)权3 → find(1)=find(3)，已连通，跳过
加边(3,4)权4 → unite成功，cnt=3=n-1，total=7

输出：7

核心思路：

1. 先记录所有操作
2. 从后向前处理：block 变成 connect，正向的 connect 但时间上在 block 之前需要排除
3. 用并查集 + 离线逆序处理，输出时逆序输出 query 结果

更简洁的方案：预处理每条边「实际存在的时间段」，再用离线并查集。

以下给出离线逆序 + 回收操作的简化版本（假设每对服务器最多断开一次）：

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<tuple<int,int,int>> ops(m);  // {type, a, b}，type: 0=connect,1=query,2=block
    set<pair<int,int>> blocked;         // 已断开的边
    
    for (auto& [t, a, b] : ops) {
        string op; cin >> op >> a >> b;
        if (op == "connect") t = 0;
        else if (op == "query") t = 1;
        else { t = 2; blocked.insert({min(a,b), max(a,b)}); }
    }
    
    // 逆序处理
    DSU dsu(n);
    // 先加入所有「最终状态下存在」的边（connect 且未被 block 的）
    for (auto& [t, a, b] : ops) {
        if (t == 0) {
            auto key = make_pair(min(a,b), max(a,b));
            if (!blocked.count(key)) dsu.unite(a, b);
        }
    }
    
    vector<string> answers;
    for (int i = m - 1; i >= 0; i--) {
        auto [t, a, b] = ops[i];
        if (t == 2) {
            // 逆序时 block 变 connect
            dsu.unite(a, b);
        } else if (t == 1) {
            answers.push_back(dsu.connected(a, b) ? "YES" : "NO");
        }
        // connect 在逆序中不处理（已在初始化时加入）
    }
    
    reverse(answers.begin(), answers.end());
    for (auto& s : answers) cout << s << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int pa[MAXN], sz_arr[MAXN];
long long dist[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) { pa[i] = i; sz_arr[i] = 1; dist[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    dist[x] += dist[pa[x]];
    pa[x] = root;
    return root;
}

// 声明 height[b] - height[a] = d，返回 false 表示矛盾
bool add_info(int a, int b, long long d) {
    int ra = find(a), rb = find(b);
    long long da = dist[a], db = dist[b];
    if (ra == rb) return (db - da == d);
    if (sz_arr[ra] < sz_arr[rb]) { swap(ra, rb); swap(da, db); d = -d; }
    pa[rb] = ra;
    dist[rb] = d + da - db;
    sz_arr[ra] += sz_arr[rb];
    return true;
}

int main() {
    int n, m, q;
    cin >> n >> m;
    init(n);
    
    bool global_conflict = false;
    for (int i = 0; i < m; i++) {
        int a, b; long long d;
        cin >> a >> b >> d;
        if (!add_info(a, b, d)) global_conflict = true;
    }
    
    cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        int ra = find(a), rb = find(b);
        if (ra != rb) cout << "unknown\n";
        else if (global_conflict) cout << "conflict\n";
        else cout << dist[b] - dist[a] << "\n";
    }
    return 0;
}

输入示例：

5 3
1 2 3    → height[2] - height[1] = 3
2 3 5    → height[3] - height[2] = 5
1 3 8    → height[3] - height[1] = 8（与前两条一致）

2
1 3      → 输出 8
1 4      → 输出 unknown

用带权并查集，dist[x] 记录奇偶性（0=未翻转，1=翻转过奇数次）：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int pa[MAXN];
int flip[MAXN];  // flip[x] = x 相对于根的翻转次数（mod 2）

void init(int n) {
    for (int i = 0; i <= n; i++) { pa[i] = i; flip[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    flip[x] ^= flip[pa[x]];  // 路径上翻转次数的奇偶叠加
    pa[x] = root;
    return root;
}

// 声明「x 和 y 属于同组，且翻转关系为 d（0=同色，1=不同色）」
void unite(int x, int y, int d) {
    int rx = find(x), ry = find(y);
    int fx = flip[x], fy = flip[y];
    if (rx == ry) return;
    pa[ry] = rx;
    flip[ry] = d ^ fx ^ fy;
}

// 查询 x 的颜色相对于根的偏移
int query(int x) {
    find(x);
    return flip[x];
}

此模板适用于所有「奇偶关系」类型的种类并查集问题。

这是标准并查集裸题，直接套模板：

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) dsu.unite(x, y);
        else cout << (dsu.connected(x, y) ? "Y" : "N") << "\n";
    }
    return 0;
}

直接使用 3.13.8 节的「种类并查集」代码，注意细节：

• 自己吃自己（x == y 且 type=2）：假话
• 编号越界（x > n 或 y > n）：假话
• 矛盾检测先于合并

// 直接使用 3.13.8 节代码即可
// 关键测试：
// N=100, K=7
// 1 101 1    → x=101 > N=100，假话，lies=1
// 2 1 2      → 声明 1 吃 2，无矛盾，合并
// 2 2 3      → 声明 2 吃 3，无矛盾，合并  
// 2 3 1      → 1 吃 2 吃 3 吃 1 ← 合法循环
// 1 1 3      → 1 和 3 同类？但 1 吃 3，矛盾，lies=2
// 2 3 3      → x==y，自己吃自己，lies=3
// 1 1 2      → 1 和 2 同类？但 1 吃 2，矛盾，lies=4
// 输出：4

完整代码见 3.13.8 节，直接提交即可。

为什么不能路径压缩？ 路径压缩会改变树的结构，版本回滚后结构会乱。只用按秩合并（树高 O(log N)），每次 find 最多 O(log N) 步，可接受。

// 可持久化并查集框架（用持久化线段树维护 pa[]）
// 每次 unite 操作只改动 2 个节点（rx 和 ry），
// 对线段树做单点修改，生成新版本

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXLOG = 20;

struct Node {
    int left, right, val, rnk;  // rnk = 树的秩
} tr[MAXN * MAXLOG * 4];

int root[MAXN], cnt = 0;  // root[i] = 第 i 个版本的根节点

// 建初始线段树（所有节点 pa[i] = i）
int build(int l, int r) {
    int node = ++cnt;
    if (l == r) {
        tr[node].val = l;  // pa[l] = l（自己是根）
        tr[node].rnk = 0;
        return node;
    }
    int mid = (l + r) / 2;
    tr[node].left = build(l, mid);
    tr[node].right = build(mid + 1, r);
    return node;
}

// 持久化单点修改 pa[pos] = new_val
int update(int prev, int l, int r, int pos, int new_val, int new_rnk = -1) {
    int node = ++cnt;
    tr[node] = tr[prev];  // 复制上一版本
    if (l == r) {
        tr[node].val = new_val;
        if (new_rnk >= 0) tr[node].rnk = new_rnk;
        return node;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        tr[node].left = update(tr[prev].left, l, mid, pos, new_val, new_rnk);
    else
        tr[node].right = update(tr[prev].right, mid + 1, r, pos, new_val, new_rnk);
    return node;
}

// 查询 pa[pos]
int query(int node, int l, int r, int pos) {
    if (l == r) return tr[node].val;
    int mid = (l + r) / 2;
    if (pos <= mid) return query(tr[node].left, l, mid, pos);
    return query(tr[node].right, mid + 1, r, pos);
}

int n;

// 在版本 ver 中查找 x 的根（不做路径压缩！）
int find(int ver, int x) {
    int pa = query(root[ver], 1, n, x);
    if (pa == x) return x;
    return find(ver, pa);
}

int main() {
    int m;
    cin >> n >> m;
    root[0] = build(1, n);
    
    for (int i = 1; i <= m; i++) {
        int op; cin >> op;
        if (op == 1) {
            // 合并
            int x, y; cin >> x >> y;
            int rx = find(i - 1, x), ry = find(i - 1, y);
            // ... 按秩合并，生成 root[i]
        } else if (op == 2) {
            // 回滚到第 k 版本
            int k; cin >> k;
            root[i] = root[k];
        } else {
            // 查询
            int x; cin >> x;
            cout << find(i - 1, x) << "\n";
            root[i] = root[i - 1];
        }
    }
    return 0;
}

完整实现参考：Luogu P3402 可持久化并查集