问题描述
你现在是城市的主人
现在有 个村庄，要修建 条路，每修建一条路，道路是双向的，输出至少还需要修建几条，可以让所有村庄互相可达。
一开始路为 条
数据保证有解
输入格式
第一行两个整数 ,
接下来有 行，每行 代表修建了一条从第 个村庄，到第 个村庄的路。
和 可能相同。
输出格式
一共 行，第 个数代表已经修建了前 条路时，最少还需要修建几条，可以让所有村庄互相可达。
样例输入
5 5
1 1
1 2
2 3
4 4
1 2
样例输出
4
3
2
2
2
#include <bits/stdc++.h>
using namespace std;
int par[100005], n, m, a, b, cnt = 0;
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y)
return false;
par[x] = y;
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
par[i] = i;
for (int i = 0; i < m; ++i) {
scanf("%d%d", &a, &b);
if (unite(a, b))
cnt++;
printf("%d\n", n - cnt - 1);
}
return 0;
}