修复公路

链接 此题我们需要判断什么时间所有村庄都连通了,由于施工是同时进行的,我们可以按时间将不同公路排个序

如何知道村庄都连通了,我们只需将这些公路两边的村庄进行合并,如何合并呢?就是并查集的方法,这里我将根节点设为负数,这样我们只需要知道还剩多少个负数就行了

但是,写着写着,我发现有个更简单的方法,我们只需设置一个计数器,对合并函数(Union)做一个小小的修改。当两个子节点查询到的根节点相同时,记为合并失败,返回-1,反之返回1

这样如果计数器为1时我们就提前退出并输出当前施工的时间(由于是按时间大小排序的,所以这个时间就是最小时间),反之如果没有退出说明无法相通,输出-1

代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>arr;

int Find(int x) {
	if (arr[x] < 0) {
		return x;
	}
	else {
		return arr[x] = Find(arr[x]);
	}
}

bool Union(int x,int y) {
	int root_x = Find(x);
	int root_y = Find(y);
	if (root_x != root_y) {
		if (arr[root_x] < arr[root_y]) {
			//x更多
			arr[root_x] += arr[root_y];
			arr[root_y] = root_x;
		}
		else if(arr[root_x]>arr[root_y]) {
			//y更多
			arr[root_y] += arr[root_x];
			arr[root_x] = y;
		}
		else {
			arr[root_x] += arr[root_y];
			arr[root_y] = root_x;
		}
		return 1;
	}
	return 0;
}

struct Road {
	int x, y;
	int time;
	bool operator <(const Road& other)const {
		return time < other.time;
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<Road>village(m);
	arr.resize(n + 1, -1);
	for (int i = 0;i < m;i++) {
		cin >> village[i].x >> village[i].y >> village[i].time;
	}
	sort(village.begin(), village.end());
	int count = n;
	for (int i = 0;i < m;i++) {
		if (Union(village[i].x, village[i].y)) {
			count--;
		}
		if (count == 1) {
			cout << village[i].time;
			return 0;
		}
	}
	cout << -1;
}

时间复杂度:O(m log m)

空间复杂度:O(n + m)