Java Coding Test Course, Union Find

In this article, we will explain the Union-Find data structure in detail through algorithm problems and implement it in Java. In particular, we will select problems that are frequently asked in coding tests and proceed with the process of writing actual code.

What is Union-Find?

Union-Find is a data structure used to manage ‘disjoint sets’, which is useful for finding connected components in graphs or determining whether two specific elements belong to the same set. The main operations of this data structure are twofold.

  • Find: An operation that finds the set to which an element belongs.
  • Union: An operation that merges two sets.

Problem Description

The problem we will solve now is Counting Connected Components. Given n vertices and m edges, the task is to count the number of connected components. A connected component is a set of vertices that are connected in the graph.

For example, consider the graph below. If there are 5 vertices and the edges are as follows,

            1 - 2
            |   |
            3 - 4
            5
        

the connected components are {1, 2, 3, 4} and {5}, totaling two components.

Problem Definition

        Given the number of vertices n and a list of edges, output the number of connected components.

        Input: 
        n = 5
        edges = [[1, 2], [1, 3], [2, 4]]

        Output: 2
    

Approach to Solve the Problem

This problem can be solved using Union-Find. As we visit each node, we check which set the node belongs to, and when a new connection is discovered, we unify the sets through the union operation. Finally, we can count the number of distinct sets to determine the number of connected components.

Implementing Union-Find

To implement Union-Find, we will define two functions. One is the find function, which finds the parent of a specific element, and the other is the union function, which connects two elements.

Java Code Implementation

        public class UnionFind {
            private int[] parent;
            private int[] rank;

            public UnionFind(int n) {
                parent = new int[n + 1];
                rank = new int[n + 1];
                for (int i = 1; i <= n; i++) {
                    parent[i] = i;  // Initialize each node's parent to itself
                    rank[i] = 0;    // Initial rank is 0
                }
            }

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

            public void union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX != rootY) {
                    if (rank[rootX] > rank[rootY]) {
                        parent[rootY] = rootX;
                    } else if (rank[rootX] < rank[rootY]) {
                        parent[rootX] = rootY;
                    } else {
                        parent[rootY] = rootX;
                        rank[rootX]++;
                    }
                }
            }

            public int countComponents(int n, int[][] edges) {
                // Perform union operation using edges
                for (int[] edge : edges) {
                    union(edge[0], edge[1]);
                }
                // Count the number of connected components
                HashSet componentRoots = new HashSet<>();
                for (int i = 1; i <= n; i++) {
                    componentRoots.add(find(i));
                }
                return componentRoots.size();
            }
        }
    

Main Function

        public class Main {
            public static void main(String[] args) {
                UnionFind uf = new UnionFind(5);
                int[][] edges = {{1, 2}, {1, 3}, {2, 4}};
                int result = uf.countComponents(5, edges);
                System.out.println("Number of connected components: " + result);  // Output: 2
            }
        }
    

Code Analysis

The above code creates a UnionFind class and implements the union-find algorithm. The constructor initializes the values and ranks of each node, and implements the find and union functions. The find function uses path compression to reduce time complexity, while the union function uses rank to maintain balance.

Conclusion

Union-Find is a very useful data structure for graph problems. Through the problem of counting connected components presented earlier, I hope you have laid a foundation for understanding Union-Find. Since this data structure can be asked in various forms in actual coding tests, understanding it is essential. I hope you continue to solve various problems using Union-Find to deepen your understanding and improve your skills.