转载自https://blog.silvery.me/

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。所有道路都是双向的。

省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。

问题：问最少还需要建设多少条双向道路？

输入格式

第 1 行给出两个正整数，分别是城镇数目 N 和道路数目 M。

随后的 M 行对应 M 条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。

为简单起见，城镇从 1 到 N 编号。

注意：两个城市之间可以有多条道路相通。也就是说，以下输入也是合法的：

3 3
1 2
1 2
2 1

输出格式

输出一个整数，表示最少还需要建设的道路数目。

数据范围

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000

输入样例

4 2
1 3
4 3

输出样例

1

题目分析

并查集
这道题可以很容易抽象成集合问题，只需要实现所有的点都在同一集合即可。
代码中，通过输入条件，我们可以将点放在一些集合中。
我们再枚举每个点到其他所有点，如果不在一个集合，那么答案加一，并且将这两点连接起来。

代码实现

#include <iostream>
#include <vector>
using namespace std;

class Unifind {
    int n;
    vector <int> p;
public:
    Unifind(int num) : n(num + 1) {
        p.resize(n);
        for (int i = 0; i < n; ++i) p[i] = i;
    }
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    void merge(int i, int j) {
        p[find(j)] = find(i);
    }
};
int n, m, a, b, cnt;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    Unifind uf(n);
    while(m--) {
        cin >> a >> b;
        uf.merge(a,b);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (uf.find(i) != uf.find(j)) {
                uf.merge(i,j);
                ++cnt;
            }
        }
    }
    cout << cnt;
    return 0;
}