C++ Coding Test Course, Union Find

The Union-Find data structure is very useful for solving algorithmic problems. In this article, we will explain the concept of Union-Find and detail the problem-solving process using C++.

What is Union-Find?

The Union-Find algorithm is a data structure that efficiently manages a collection of data. This data structure is also known as Disjoint Set and primarily supports the following two operations:

  • Find: This operation finds which set a particular element belongs to. It returns the representative element (root node) of the set.
  • Union: This operation merges two sets. It connects the root nodes of the two sets to form one set.

It is mainly used to find cycles in graph theory or to check connected components. There are two optimization techniques to effectively utilize Union-Find:

1. Path Compression

When performing the Find operation, it updates the parent of all nodes along the path to the root node, allowing for faster retrieval of the root node in subsequent operations.

2. Rank-based Union

When performing the Union operation, it compares the sizes of two sets and connects the smaller set as a child of the larger set. This helps to reduce the height of the tree.

Problem Description

Now, let’s look at a problem that can be solved using the Union-Find algorithm. We will solve the problem below.

Problem: Friend Network

There is a friend network in which several friends are connected to each other. Each friend is identified by a number from 1 to N. Two friends are considered friends if they are directly or indirectly connected. Given a pair of friends (a, b), check whether a and b belong to the same friend group in the friend network.

Input Format

  • The first line contains the number of friends N and the number of friend relationships M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
  • From the second line onward, M pairs of friend relationships a, b are given.
  • The last line contains the query Q, where each query provides a pair of friends (x, y).

Output Format

For each query, print ‘YES’ if x and y belong to the same friend group, otherwise print ‘NO’.

Algorithm Approach

  1. Initialize and connect the friend relationships using Union-Find. Use Union(a, b) to connect a and b in the same set.
  2. For each query, use Find(x) and Find(y) to check the root nodes of the two friends. If they have the same root node, print ‘YES’; otherwise, print ‘NO’.

C++ Code Implementation

Below is the C++ code that implements the Union-Find algorithm:


#include 
#include 
using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // Rank-based union
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector parent;
    vector rank;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        uf.unionSets(a, b);
    }

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        if (uf.find(x) == uf.find(y)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

Code Explanation

In the above C++ code, we implemented the following components:

  • UnionFind class: Contains the main logic of the Union-Find algorithm. The find function finds the root node, and the unionSets function merges two sets.
  • Main function: Takes the friend relationships as input, stores them in the Union-Find structure, and outputs the results for the given queries.

Time Complexity

The time complexity of the Union-Find algorithm is as follows:

  • Find operation: Almost constant time (α(N), proportional to the inverse Ackermann function)
  • Union operation: Almost constant time

Thus, the overall time complexity of the algorithm is O(M * α(N)), where M is the number of friend relationships.

Conclusion

In this course, we have examined the concept of the Union-Find data structure and the problem-solving process using C++ in detail. Union-Find is a powerful tool that can be effectively utilized in various problems. I hope it will be of great help in your future coding tests.