Loading... 转载自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; } ``` 最后修改:2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏