Swift Coding Test Course, Union Find

Introduction

Currently, understanding algorithms and data structures is essential in the IT industry. Especially for developers preparing for employment, it is crucial to have problem-solving skills based on this knowledge. In this course, we will take a closer look at the ‘Union-Find’ algorithm and explain the problem-solving process using it step by step.

What is Union-Find?

Union-Find is a data structure primarily used to handle operations on sets, supporting two main operations:

  • Union: The operation of merging two sets
  • Find: The operation of finding which set a particular element belongs to

This data structure is useful for solving the Disjoint Set problem. Union-Find increases efficiency using optimization techniques called ‘Path Compression’ and ‘Rank’.

Problem Definition

To define the problem, let’s set up a hypothetical situation.

Problem: Given N elements, write a program to determine whether multiple pairs of elements belong to the same set.

The number of elements N and the number of pairs M are provided. For each pair, if they belong to the ‘same set’, print “YES”, and if they belong to ‘different sets’, print “NO”.

Example Problem

Input: 

5 4
1 2
1 3
2 3
4 5
1 4

Output: 

NO
YES

In the above example, the first pair (1, 4) belongs to different sets, so it outputs “NO”, and the second pair (1, 4) belongs to the same set, so it outputs “YES”.

Implementing the Union-Find Algorithm

Now, let’s implement the Union-Find algorithm in Swift. We will write the code reflecting the basic concepts. 

class UnionFind {
    private var parent: [Int]
    private var rank: [Int]
    
    init(size: Int) {
        self.parent = Array(0.. Int {
        if p != parent[p] {
            parent[p] = find(parent[p]) // Path Compression
        }
        return parent[p]
    }
    
    func union(_ p: Int, _ q: Int) {
        let rootP = find(p)
        let rootQ = find(q)
        
        if rootP != rootQ {
            if rank[rootP] > rank[rootQ] {
                parent[rootQ] = rootP
            } else if rank[rootP] < rank[rootQ] {
                parent[rootP] = rootQ
            } else {
                parent[rootQ] = rootP
                rank[rootP] += 1
            }
        }
    }
}

Problem Solving Process

To solve the problem, we will follow these steps.

  1. Parse the input to obtain the number of elements N and the number of pairs M.
  2. Use the UnionFind class to manage the sets of elements.
  3. Perform the union operation for each pair to merge the sets.
  4. Perform the find operation for each pair and print the results.

The code is as follows. 

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]
let m = input[1]

let unionFind = UnionFind(size: n + 1)

for _ in 0..

Conclusion

In this course, we have implemented the theoretical background of the Union-Find algorithm and the problem-solving process in Swift. Union-Find is one of the very useful data structures for graph-related problems. By utilizing this data structure, complex problems can be effectively solved.

I hope you continue to explore various algorithms to aid in your coding test preparation, and I look forward to introducing other algorithms in the next course.