data-structures-for-disjoint-sets

Name: data-structures-for-disjoint-sets
Availability: InStock
Author: 4rcadia

Explain disjoint-set union-find operations and partition invariants with performance bounds.

7|Updated Apr 24, 2026

Search Tags:#graphs #data-structures #algorithm-analysis #union-find #path-compression #disjoint-set #inverse-ackermann

Ready to run

npx skills add https://github.com/Arcadi4/nerdy --skill data-structures-for-disjoint-sets

💬 Prompt for ChatGPT / Claude Chat▼

Please help me install this Agent Skill.
Skill: data-structures-for-disjoint-sets
Source: https://github.com/Arcadi4/nerdy/tree/main/clrs/data-structures-for-disjoint-sets
Command: npx skills add https://github.com/Arcadi4/nerdy --skill data-structures-for-disjoint-sets

SYSTEM DOCUMENTATION & REQUIREMENTS

What problem does it solve?

This skill helps you reason about disjoint-set data structures (union-find) and correctness of MAKE-SET, FIND-SET, and UNION, while comparing representations (linked lists vs forests) and their impact on performance invariants.

Core Features & Use Cases

Understand partition invariants and representative contracts for dynamic connectivity problems.
Analyze performance bounds including amortized costs and inverse-Ackermann, across union-by-rank and path compression variants.
Apply to offline algorithms such as offline minimum and Tarjan offline LCA, as well as general incremental connectivity tasks.

Quick Start

Run a complete DSU walkthrough: initialize sets with MAKE-SET, perform unions for graph edges, then answer connectivity queries with FIND-SET.

Frequently Asked Questions about data-structures-for-disjoint-sets

High-intent search queries and answers about installing and using this skill.

FAQPage Schema

How do union-find data structures maintain partition invariants for dynamic connectivity?▼

Union-find structures maintain partition invariants by grouping elements into disjoint sets using MAKE-SET, FIND-SET, and UNION operations, ensuring each element belongs to exactly one set and connectivity queries are answered efficiently.

What is the amortized time complexity of disjoint-set operations with path compression and union-by-rank?▼

The amortized complexity of disjoint-set operations with path compression and union-by-rank is bounded by the inverse-Ackermann function, providing near-constant time per operation across long sequences of unions and finds.

How do I apply union-find to offline algorithms like offline minimum and Tarjan offline LCA?▼

Apply union-find to offline algorithms by processing queries or elements in reverse order, using UNION operations to merge sets and FIND-SET to locate representatives, enabling efficient offline minimum and Tarjan offline LCA computation.

Linked list vs forest representation for disjoint sets: which approach performs better?▼

Forest representations with union-by-rank and path compression outperform linked list representations for disjoint sets, achieving inverse-Ackermann amortized bounds instead of linear time, making forests better for large-scale connectivity problems.

When should I use disjoint-set data structures for incremental connectivity problems?▼

Use disjoint-set data structures for incremental connectivity problems when edges are only added and you need to answer connectivity queries efficiently, as DSU provides near-constant amortized time per union and find operation.