NC 14685 并查集

题意

传送门 NC 14685

题解

并查集求连通块个数 $n$，则至少需要增加 $n-1$ 条边，使图的任意节点连通。

#include <bits/stdc++.h> using namespace std; #define maxn 100005 typedef long long ll; int n, m, par[maxn], rnk[maxn]; void init(int n) { for (int i = 1; i <= n; i++) { par[i] = i, rnk[i] = 0; } } int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (rnk[x] > rnk[y]) par[y] = x; else { par[x] = y; if (rnk[x] == rnk[y]) ++rnk[y]; } } int main() { scanf("%d%d", &n, &m); init(n); while (m--) { int u, v; scanf("%d%d", &u, &v); unite(u, v); } int res = 0; for (int i = 1; i <= n; i++) { if(find(i) == i) ++res; } printf("%d\n", res - 1); return 0; }