福州大仙2018年复试上机真题1
程序员文章站
2022-03-13 16:35:17
...
一,问题描述
二,问题分析
该问题我们采用并查集的数据结构来思考
1.最开始初始化,每个城镇都是孤立的节点,其父节点就是本身
2.道路相通意味着 两个节点有道路相连,即属于同于同一个集合,根据输入的道路相连情况,依次对其进行 并查集的union() 操作,合并到同一个节点
3.最后通过find()操作依次找到所有城镇的祖先节点,并存入集合set中,集合的大小即为城镇划分的数量
4.注意:n个城镇,最少只需要n-1条道路即可相连通
三,代码解答
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int find(vector<int> res, int num) { //寻找根节点,返回根节点
int root = num;
while (res[root] != root)
root = res[root];
return root;
}
void union1(vector<int> &res, int x, int y) { //把x,y两个集合合并,y为x的父节点
int root1 = find(res, x);
int root2 = find(res, y);
if (root1 != root2) { //根节点相同说明在同一个集合中
res[root1] = root2;
}
}
int main() {
int n, m; //n城镇数目,m街道数目
while (cin >> n >> m) {
if (m == 0) {
cout << 0 << endl;
}
set<int> res; //记录城镇的集合
vector<int> towm(n + 1); //多开辟一位空间,保证下标可以到达n
for (int i = 0; i < n + 1; i++) { //并查集的初始化
towm[i] = i;
}
for (int i = 0; i < m; i++) { //对道路情况进行合并操作
int a, b;
cin >> a >> b;
union1(towm, a, b);
}
int root;
for (int i = 0; i < n+1; i++) { //得到所有城镇的根节点,并存入set中
root = find(towm, i);
res.insert(root);
}
cout <<res.size()-2 << endl; //res.size()-2 要减去0整个多开辟的空间 n个城镇最好只要n-1个道路
}
return 0;
}
下一篇: FOJ 1476 矩形的个数
推荐阅读