Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

A concept,

His idea is that an array represents the whole forest (parent), and the root node of the tree uniquely identifies a set. As long as we find the root of an element, we can determine which set it is in. He has two operations:

  • Union: To combine two disjoint sets into a single set.
  • Find: Queries whether two elements are in the same collection. The determination method is to keep looking up to find its root node, which can be used to determine whether two elements belong to the same subset.

Second, the operating

Each set is represented by a tree. The number of the root is the number of the whole set. Each node stores its parent, parents[x] representing the parent of X.

2.1 the initialization

The important idea of looking up a set is to represent the set by an element of the set. Since each set has only one point to start with, you can simply make itself the parent node. Parents [x] = x is a sign of a parent node because parents[x] stores the parent node of X unless it is a parent node.

So the current parents array should be

i 1 2 3 4 5
parents[i] 1 2 3 4 5

2.2 combined

When we want a set of nodes to join another set of nodes, use the merge operation to modify the value of their parents array. For example, if we want to merge 2 and 3 and 4 and 5, modify parents[3] = 2 and parents[5] = 4

i 1 2 3 4 5
parents[i] 1 2 2 4 4

In this case, we want to add the set of 4 to the set of 2, so modify parents[4] = 2 in the same way

i 1 2 3 4 5
parents[i] 1 2 2 2 4

2.3 find

In this method, the parent array is used to continuously search for the ancestor of X until the parent of a node is found to be himself, that is, the most ancestor node of the node. His pseudocode looks like this

while(Parents [node]! = parents) {parents = parents[parents]}Copy the code
For example, in the figure above, we want to find the ancestor of node 5:1. Find parents[5] = 4 2. Find parents[4] = 2 3. Find parents[2] = 2, return node 2Copy the code

2.4 Path Compression

The above method is the most basic representation of a roundup forest. It is no better than the linked list method because the trees created can be severely unbalanced and can therefore be optimized with path compression.

Path compression is a way of flattening a tree structure while performing a lookup. The key is that each node on the path can be directly connected to the root; They all have the same notation. To achieve this effect, when Find finds a node, it changes the references of all of that node’s ancestors to the root node in turn. The resulting tree will be flatter, speeding up future operations that reference nodes directly or indirectly.

Three, code implementation

vector<int> parents;// Store the parent node/ancestor node of each node

// The parent of all nodes is itself
void initialparent(int nodenum)
{
	parents.resize(nodenum, - 1);
	for (int i = 0; i < nodenum; i++) { parents[i] = i; }}// Find the ancestor node of the node and compress the path for all ancestors of the node
int find(int node)
{
	// Find the most ancestral node
	int r = node;
	while(parents[r] ! = r) { r = parents[r]; }int t = node;
	// Compression path
	while(t ! = r)//t is all nodes from this node up to the ancestor node r
	{
		int temp = parents[t];
		parents[t] = r;
		t = temp;
	}
	return r;
}

// Merge a set of two nodes
void merge(int x,int y)
{
	int r1 = find(x);
	int r2 = find(y);
	if (r1 == r2)
		return;
	if (parents[r1] > parents[r2]) {
		parents[r1] = r2;
	}
	else{ parents[r2] = r1; }}Copy the code