95 lines
1.9 KiB
C++
95 lines
1.9 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
|
||
using namespace std;
|
||
|
||
/*
|
||
并查集（Disjoint Set Union）
|
||
支持：
|
||
- 路径压缩
|
||
- 按集合大小合并
|
||
*/
|
||
struct DSU {
|
||
vector<int> parent; // parent[x]：x 的父节点
|
||
vector<int> sz; // sz[x]：以 x 为根的集合大小
|
||
int components; // 当前连通分量个数（可选）
|
||
|
||
// 构造函数：初始化 n 个元素（编号 0 ~ n-1）
|
||
DSU(int n = 0) {
|
||
init(n);
|
||
}
|
||
|
||
// 初始化
|
||
void init(int n) {
|
||
parent.resize(n);
|
||
sz.assign(n, 1);
|
||
components = n;
|
||
|
||
for (int i = 0; i < n; i++) {
|
||
parent[i] = i; // 初始时，每个节点都是自己的父节点
|
||
}
|
||
}
|
||
|
||
// 查找 x 的根（带路径压缩）
|
||
int find(int x) {
|
||
if (parent[x] != x) {
|
||
parent[x] = find(parent[x]); // 路径压缩
|
||
}
|
||
return parent[x];
|
||
}
|
||
|
||
// 合并 x 和 y 所在的集合
|
||
// 如果本来就在同一集合，返回 false
|
||
bool unite(int x, int y) {
|
||
int rx = find(x);
|
||
int ry = find(y);
|
||
|
||
if (rx == ry) return false;
|
||
|
||
// 按集合大小合并：小的挂到大的
|
||
if (sz[rx] < sz[ry]) {
|
||
swap(rx, ry);
|
||
}
|
||
|
||
parent[ry] = rx;
|
||
sz[rx] += sz[ry];
|
||
components--; // 连通分量减少
|
||
|
||
return true;
|
||
}
|
||
|
||
// 判断 x 和 y 是否在同一集合
|
||
bool same(int x, int y) {
|
||
return find(x) == find(y);
|
||
}
|
||
|
||
// 返回 x 所在集合的大小
|
||
int size(int x) {
|
||
return sz[find(x)];
|
||
}
|
||
};
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
int n, m;
|
||
cin >> n >> m;
|
||
|
||
DSU dsu(n);
|
||
|
||
/*
|
||
示例：
|
||
m 次操作，每次合并两个点
|
||
*/
|
||
for (int i = 0; i < m; i++) {
|
||
int a, b;
|
||
cin >> a >> b;
|
||
dsu.unite(a, b);
|
||
}
|
||
|
||
cout << dsu.components << '\n';
|
||
|
||
return 0;
|
||
}
|