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

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

问题:问最少还需要建设多少条双向道路?

输入格式

第 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;
}
分类: UnionFind

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status