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

Disjoint Set Union (DSU)

Disjoint Set Union (DSU) is a data structure that maintains a collection of non-overlapping sets and efficiently supports merging two sets and checking whether two elements belong to the same set.

Explanation

Overview

DSU, also known as Union-Find, manages a collection of disjoint sets. Each set is represented by a representative element called its root. The structure is especially useful when relationships between elements change through repeated merge operations.

How it works

Initially, every element belongs to its own individual set.; Each set has a representative or root element.; The Find operation identifies the representative of an element's set.; The Union operation combines the sets containing two specified elements.; After merging, both sets share the same representative.

Key concepts

Disjoint sets; Set representatives; Parent arrays; Find operation; Union operation; Dynamic connectivity

Time complexity

operation: MakeSet; complexity: O(1); operation: Find; complexity: O(n) in the worst case without optimizations; operation: Union; complexity: Depends on the implementation of Find and the merging strategy

Space complexity

O(n), where n is the number of elements.

Example

description: Consider five elements: 1, 2, 3, 4, and 5.; operations: Initially: {1}, {2}, {3}, {4}, {5}; Union(1, 2): {1, 2}, {3}, {4}, {5}; result: Elements 1, 2, 3, and 4 belong to the same set, while element 5 remains separate.

Applications

Connected-component detection; Kruskal's minimum spanning tree algorithm; Network connectivity; Grouping related objects; Cycle detection in undirected graphs

Example or application

Description

Consider five elements: 1, 2, 3, 4, and 5.

Operations

  • Initially: {1}, {2}, {3}, {4}, {5}

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

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

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

  • Find(4) and Find(1) return the same representative.

Result

Elements 1, 2, 3, and 4 belong to the same set, while element 5 remains separate.

Definition

DSU, also known as Union-Find, manages a collection of disjoint sets. Each set is represented by a representative element called its root. The structure is especially useful when relationships between elements change through repeated merge operations.

How It Works

  • Initially, every element belongs to its own individual set.

  • Each set has a representative or root element.

  • The Find operation identifies the representative of an element's set.

  • The Union operation combines the sets containing two specified elements.

  • After merging, both sets share the same representative.

Core Operations

OperationDescription

MakeSet(x)

Creates a new set containing only element x.

Find(x)

Returns the representative of the set containing x.

Union(x, y)

Combines the two sets containing x and y.

Implementation

Description

A common DSU implementation uses an array named parent, where parent[x] stores the parent of element x. A root element is identified when parent[x] equals x.

Pseudocode

  • MakeSet(x):

  • parent[x] = x

  • Find(x):

  • while parent[x] != x:

  • x = parent[x]

  • return x

  • Union(x, y):

  • rootX = Find(x)

  • rootY = Find(y)

  • if rootX != rootY:

  • parent[rootY] = rootX

Time Complexity

OperationComplexity

MakeSet

O(1)

Find

O(n) in the worst case without optimizations

Union

Depends on the implementation of Find and the merging strategy

Space Complexity

O(n), where n is the number of elements.

Key Concepts

  • Disjoint sets

  • Set representatives

  • Parent arrays

  • Find operation

  • Union operation

  • Dynamic connectivity

Advantages

  • Efficiently maintains groups of connected elements.

  • Supports repeated set-merging operations.

  • Uses relatively little memory.

  • Can be optimized to achieve nearly constant amortized operation time.

Limitations

  • Standard DSU supports merging sets but does not naturally support splitting them.

  • It does not directly maintain every relationship inside a set.

  • Additional structures may be required for more complex queries.

Applications

  • Connected-component detection

  • Kruskal's minimum spanning tree algorithm

  • Network connectivity

  • Grouping related objects

  • Cycle detection in undirected graphs

Related Topics

  • Union-Find Data Structure

  • Path Compression

  • Union by Rank

  • Graph Algorithms

  • Minimum Spanning Trees

Practice Questions

QuestionAnswer

What is the main purpose of DSU?

To maintain disjoint sets and efficiently merge them or determine whether elements belong to the same set.

What does Find return?

The representative or root of the set containing the specified element.

Can standard DSU efficiently split a set?

No. Standard DSU is designed primarily for merging sets.

Learning Objectives

  • Explain the central idea and purpose of disjoint set union (dsu).

  • Identify the assumptions, inputs, and conditions relevant to disjoint set union (dsu).

  • Evaluate an application of disjoint set union (dsu) 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