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 HashSetcomponentRoots = 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.