并查集实践

是不是亲戚问题

我们使用merge的优化，就不使用find的优化了

#include <iostream>
#include <vector>

using namespace std;

int SIZE = 0;
int* parent = nullptr;   // 记录每个节点的父节点
int* height = nullptr;   // 记录根节点的层高


// 返回x所在树的根节点的编号
int find_root(int x) {
    
	if (x <= 0 || x >= SIZE) {
    
		return -1;
	}

	while (x != parent[x]) {
    
		x = parent[x];
	}
	return x;
}


// 合并x和y所在的集合
void merge(int x, int y) {
    
	x = find_root(x);
	y = find_root(y);
	if (x != y) {
    
		// 这里x和y都是根节点，谁矮谁作为孩子节点
		if (height[x] > height[y]) {
    
			parent[y] = x;
		}
		else {
    
			if (height[x] == height[y]) {
    
				// y作为合并以后树的根，根节点高度要+1
				height[y]++;
			}
			parent[x] = y;
		}
	}
}

int main() {
    
	int m = 0;
	int p = 0;
	int n = 0;
	cin >> n >> m >> p;
	SIZE = n + 1;
	parent = new int[SIZE];
	height = new int[SIZE];

	for (int i = 0; i < SIZE; i++) {
    
		height[i] = 1;
		parent[i] = i;  // 一开始，每个节点的父节点就是自己
	}

	int p1, p2; // 两个人
	for (int i = 0; i < m; i++) {
    
		cin >> p1 >> p2;
		merge(p1, p2);
	}
	vector<pair<int, int>> query;
	for (int i = 0; i < p; i++) {
    
		cin >> p1 >> p2;
		query.push_back(pair<int, int>(p1, p2));
	}
	for (auto q : query) {
    
		cout << (find_root(q.first) == find_root(q.second) ? "YES" : "NO") << endl;
	}

	delete[] parent;
	delete[] height;
	parent = nullptr;
	height = nullptr;
	return 0;
}


/* 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 */

躲避拥堵的最佳路线

3 3 1 3        # 3个区、3条边、从1区到3区
1 2 2          # 从1区到2区的拥挤度为2
2 3 1
1 3 3

题目说规划一条路径，使得经过道路的拥挤度的最大值最小。该测试用例输出2，是说我们从1区到3区，可以走1->2->3，此时拥挤度的最大值为2；也可以走1->3，此时拥挤度的最大值为3；故该测试用例输出2

我们使用kruskal算法，先从拥挤度小的边开始选取，直到连通s区和t区，这样最后一条选取的边一定是已选道路拥挤度最大的，未选道路拥挤度最小的，这样就能做到在连通的基础上所选取的最大值最小

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int* parent = nullptr;

struct Edge {
    
	Edge(int start, int end, int w)
		: start_(start)
		, end_(end)
		, w_(w)
	{
    }

	int start_;
	int end_;
	int w_;
};

// 找编号为x的节点的根节点
int find(int x) {
    
	if (x == parent[x]) {
    
		return x;
	}
	else {
    
		// find优化，查找根节点的过程中，把遍历过的节点的父节点都改成根节点
		parent[x] = find(parent[x]);
		return parent[x];
	}
}


int main(){
    
	int n, num_edge, s, t;
	cin >> n >> num_edge >> s >> t;
	parent = new int[n + 1](); // n个区，为了让编号和下标对应，多开辟一个
	vector<Edge> edges;

	int start, end, w;
	for (int i = 0; i < num_edge; i++) {
    
		cin >> start >> end >> w;
		edges.emplace_back(start, end, w);
		// 初始化parent数组
		parent[start] = start;
		parent[end] = end;
	}
	// 边进行升序排列
	sort(edges.begin(), edges.end(), 
		[](const Edge& e1, const Edge& e2) ->bool{
    
		return e1.w_ < e2.w_;
		});

	for (int i = 0; i < num_edge; i++) {
    
		int root1 = find(edges[i].start_);
		int root2 = find(edges[i].end_);
		if (root1 != root2) {
    
			// 根节点不同，可以连接
			parent[root1] = root2;
			if (find(s) == find(t)) {
    
				// 选择了新的边，才会判断是否连通了s区和t区；本轮循环没有选择新的边，则没有必要判断是否连通s区和t区
				cout << edges[i].w_ << endl;
			}
		}
	}

	delete[] parent;
	return 0;
}

/* 3 3 1 3 1 2 2 2 3 1 1 3 3 */