Practice of concurrent search

Is it relatives

We use merge The optimization of the , Don't use find It's optimized

#include <iostream>
#include <vector>

using namespace std;

int SIZE = 0;
int* parent = nullptr;   //  Record the parent node of each node 
int* height = nullptr;   //  Record the floor height of the root node 


//  return x The number of the root node of the tree 
int find_root(int x) {
    
	if (x <= 0 || x >= SIZE) {
    
		return -1;
	}

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


//  Merge x and y Where the collection is 
void merge(int x, int y) {
    
	x = find_root(x);
	y = find_root(y);
	if (x != y) {
    
		//  here x and y Are root nodes , Who is short, who is the child node 
		if (height[x] > height[y]) {
    
			parent[y] = x;
		}
		else {
    
			if (height[x] == height[y]) {
    
				// y As the root of the merged tree , The height of the root node should be +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;  //  In limine , The parent node of each node is itself 
	}

	int p1, p2; //  Two people 
	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 */

The best way to avoid congestion

3 3 1 3        # 3 Districts 、3 side 、 from 1 District to 3 District 
1 2 2          #  from 1 District to 2 The congestion degree of the district is 2
2 3 1
1 3 3

The title says to plan a path , Make the maximum value of the degree of congestion passing through the road minimum . The test case output 2, It means we started from 1 District to 3 District , You can go 1->2->3, At this time, the maximum congestion is 2; You can also go 1->3, At this time, the maximum congestion is 3; Therefore, the test case output 2

We use kruskal Algorithm , Start with the edge with less congestion , Until connected s Area and t District , In this way, the last selected edge must be the one with the greatest congestion of the selected road , The least congested road is not selected , In this way, the maximum value selected on the basis of connectivity can be minimized

#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_;
};

//  Find No x The root node of the node 
int find(int x) {
    
	if (x == parent[x]) {
    
		return x;
	}
	else {
    
		// find Optimize , In the process of finding the root node , Change the parent node of the traversed node to the root node 
		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 Districts , To make the number correspond to the subscript , Open up one more 
	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);
		//  initialization parent Array 
		parent[start] = start;
		parent[end] = end;
	}
	//  The edges are arranged in ascending order 
	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) {
    
			//  The root node is different , Can be connected 
			parent[root1] = root2;
			if (find(s) == find(t)) {
    
				//  A new edge is selected , Will judge whether it is connected s Area and t District ; No new edges are selected in this cycle , Then there is no need to judge whether it is connected s Area and t District 
				cout << edges[i].w_ << endl;
			}
		}
	}

	delete[] parent;
	return 0;
}

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