✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-207

Union-Find Data Structure

Union-Find is a data structure that maintains groups of elements and supports two main operations: finding which group an element belongs to and merging two groups.

Explanation

Overview

Union-Find is another name for the Disjoint Set Union (DSU) data structure. It represents each group as a rooted tree, where every element points to a parent and the root acts as the group's representative.

Key concepts

Root nodes; Parent pointers; Set representatives; Tree-based representation; Connectivity queries; Set merging

Time complexity

operation: Find; complexity: O(n) worst case without optimization; operation: Union; complexity: O(n) worst case when it requires an unoptimized Find

Space complexity

O(n) for storing the parent information.

Example

scenario: A software feature needs to use union-find data structure.; task: Design a small, testable solution that demonstrates union-find data structure while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of union-find data structure, and trace the result with a small representative dataset.; learningPoint: This union-find data structure example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Applications

Detecting connected components; Checking whether two graph vertices are connected; Implementing Kruskal's algorithm; Grouping network devices; Solving equivalence-relation problems

Advantages

Simple and flexible representation of disjoint groups.; Supports efficient connectivity checks after optimization.; Useful for processing large collections of relationships.; Can be combined with rank and path compression optimizations.

Example or application

Scenario

A software feature needs to use union-find data structure.

Task

Design a small, testable solution that demonstrates union-find data structure while satisfying the requirements described in this entry.

Approach

Identify the input and expected output, apply the central idea of union-find data structure, and trace the result with a small representative dataset.

Learning Point

This union-find data structure example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Definition

Union-Find is another name for the Disjoint Set Union (DSU) data structure. It represents each group as a rooted tree, where every element points to a parent and the root acts as the group's representative.

Main Operations

NameDescription

Find

Determines the representative of the group containing an element.

Union

Merges the groups containing two elements if they are different.

Representation

Description

Union-Find commonly uses a parent array to represent its groups. Each element initially points to itself. During merging, the root of one tree becomes a child of the root of another tree.

Example

  • Initial groups: {1}, {2}, {3}, {4}

  • Union(1, 2): {1, 2}, {3}, {4}

  • Union(3, 4): {1, 2}, {3, 4}

  • Union(2, 4): {1, 2, 3, 4}

Implementation

Language

Pseudocode

Code

  • parent = [0, 1, 2, 3, 4]

  • function find(x):

  • if parent[x] == x:

  • return x

  • return find(parent[x])

  • function union(a, b):

  • rootA = find(a)

  • rootB = find(b)

  • if rootA != rootB:

  • parent[rootB] = rootA

Explanation

The Find operation follows parent links until it reaches a root. The Union operation connects the roots of two different trees.

Time Complexity

OperationComplexity

Find

O(n) worst case without optimization

Union

O(n) worst case when it requires an unoptimized Find

Space Complexity

O(n) for storing the parent information.

Key Concepts

  • Root nodes

  • Parent pointers

  • Set representatives

  • Tree-based representation

  • Connectivity queries

  • Set merging

Advantages

  • Simple and flexible representation of disjoint groups.

  • Supports efficient connectivity checks after optimization.

  • Useful for processing large collections of relationships.

  • Can be combined with rank and path compression optimizations.

Limitations

  • The basic implementation can create tall trees.

  • Repeated Find operations can become expensive without optimization.

  • It is not designed for arbitrary deletion or splitting of groups.

Applications

  • Detecting connected components

  • Checking whether two graph vertices are connected

  • Implementing Kruskal's algorithm

  • Grouping network devices

  • Solving equivalence-relation problems

Related Topics

  • Disjoint Set Union

  • Path Compression and Union by Rank

  • Graph Connectivity

  • Minimum Spanning Tree

Practice Questions

QuestionAnswer

What are the two primary Union-Find operations?

Find and Union.

What does a root represent?

The representative of an entire group or set.

Why is Union-Find useful in graph algorithms?

It efficiently checks whether vertices belong to the same connected component and merges components.

Learning Objectives

  • Explain the central idea and purpose of union-find data structure.

  • Identify the assumptions, inputs, and conditions relevant to union-find data structure.

  • Evaluate an application of union-find data structure for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures