#include #include using namespace std; /* 并查集(Disjoint Set Union) 支持: - 路径压缩 - 按集合大小合并 */ struct DSU { vector parent; // parent[x]:x 的父节点 vector 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; }