Data Structures -> DSU¶

Union-find for component maintenance, offline connectivity, and Kruskal-style structure building.

Microtopics¶

Source	Type
AtCoder Library Practice Contest	`Practice`
CSES Problem Set	`Practice`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Disjoint Set Union I	`AOJ`	`Easy`	-	Implementation-Heavy	DSU Basics; Component Representatives	Intro; Online-Judge	A classic AOJ DSU starter that is ideal for practicing the raw union-find interface.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Building Roads	`CSES`	`Easy`	-	Data-Structure-Heavy; Implementation-Heavy	Connected Components; Union-Find Basics; Graphs	Components; Connectivity	A friendly first DSU problem for merging components and counting how many remain.
Road Construction	`CSES`	`Easy`	-	Data-Structure-Heavy	DSU; Component Sizes; Amortized Complexity	Dynamic-Connectivity; Largest-Component; Component-Size	A classic DSU exercise with incremental edge additions and size tracking.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Road Reparation	`CSES`	`Medium`	-	Greedy-Heavy; Data-Structure-Heavy	DSU; MST; Sorting Edges	Minimum-Spanning-Tree; Kruskal; MST	A canonical Kruskal benchmark that shows DSU in its most common graph role.
Union Find	`Library Checker`	`Medium`	-	Data-Structure-Heavy	Path Compression; Union By Size; Online Queries	Connectivity	A clean official benchmark for validating a DSU implementation against a trusted judge.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`C11XU`	Bộ sưu tập đồng xu	`primary`	`hard`	xor-independence; forest selection; augmenting exchange	Note	Code
`DYNAMICCONNECTIVITY`	Dynamic Connectivity	`secondary`	`hard`	dsu rollback; segment tree over time; offline dynamic connectivity	Note	Code
`MCQUERY`	MinCut Query	`secondary`	`hard`	all-pairs min-cut; cut tree; count pairs by threshold	Note	Code

python3 scripts/generate_problem_catalog.py