欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

福州大仙2018年复试上机真题1

程序员文章站 2022-03-13 16:35:17
...

一,问题描述

福州大仙2018年复试上机真题1

福州大仙2018年复试上机真题1

福州大仙2018年复试上机真题1 

二,问题分析

该问题我们采用并查集的数据结构来思考

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