# Disjoint Set Union — Problem Tracker

[অধ্যায়ে ফিরুন](../README.md) · [সহজ ব্যাখ্যা ও ব্যবহার](../learning-guide.md) · [উৎসের তালিকা](../source-map.md)

> **লিংক পড়ার নিয়ম:** Source খুললে প্ল্যাটফর্মের মূল প্রশ্ন, Note file খুললে এই সাইটের ব্যাখ্যা ও সমাধান পাবেন। নোটগুলো আগে থেকেই লেখা আছে। `planned` হলো আপনার ব্যক্তিগত অনুশীলনের অবস্থা, নোট অনুপস্থিত থাকার চিহ্ন নয়। প্ল্যাটফর্মের কিছু প্রশ্নে লগইন বা Premium লাগতে পারে; স্থানীয় নোট সরাসরি পড়া যাবে।

এই folder DSU-র practice problems track করে। প্রতিটা problem তার নিজের একটা note file পায় (**Note file** column-এ নাম দেওয়া), যা [../../templates/ds-problem-note-template.md](../../templates/ds-problem-note-template.md)-এর 24-section template দিয়ে লেখা — analogy, pattern, thinking tweak, dry run, complexity, mistakes, আর বাকি সব। List-টা easy থেকে hard-এ সাজানো; কয়েকটা problem ইচ্ছে করে [../../09-graphs/](../../09-graphs/README.md) থেকে repeat করা, যাতে তুমি DSU solution-টা তোমার traversal solution-এর পাশে লিখে তুলনা করতে পারো।

এই tracker কীভাবে ব্যবহার করবে:

1. link দিয়ে official statement পড়ো (main [../README.md](../README.md) practice list-এও আছে)।
2. code করার আগে দুটো প্রশ্নের উত্তর লিখে দাও: *আমি কী union করছি?* আর *সাথে কোন extra data চড়তে হবে (sizes, counts)?* বেশিরভাগ DSU problem ওই উত্তরগুলো ঠিক হওয়ার মুহূর্তেই solve হয়ে যায়।
3. কিছু দেখার আগে অন্তত 25 মিনিট চেষ্টা করো।
4. note file বানাও, template ভরো, Status `solved` (বা `revisit`)-এ সেট করো।

Status values: `planned` → `attempted` → `solved` / `revisit`।

## Tracker

| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | Find if Path Exists in Graph | Easy | [LeetCode 1971](https://leetcode.com/problems/find-if-path-exists-in-graph/) | Dynamic connectivity | `09-graphs` একই problem-এর BFS version | [001-find-if-path-exists-dsu.md](001-find-if-path-exists-dsu.md) | planned |
| 2 | Number of Provinces | Easy-Medium | [LeetCode 547](https://leetcode.com/problems/number-of-provinces/) | Component counting | `09-graphs` DFS version (ওখানে #6) | [002-number-of-provinces-dsu.md](002-number-of-provinces-dsu.md) | planned |
| 3 | Building Roads | Easy | [CSES task 1666](https://cses.fi/problemset/task/1666) | Components − 1 | `09-graphs` components | [003-building-roads-dsu.md](003-building-roads-dsu.md) | planned |
| 4 | Graph Valid Tree | Medium | [LeetCode 261](https://leetcode.com/problems/graph-valid-tree/) | Cycle detection + count | `10` union returns False insight | [004-graph-valid-tree.md](004-graph-valid-tree.md) | planned |
| 5 | Redundant Connection | Medium | [LeetCode 684](https://leetcode.com/problems/redundant-connection/) | Cycle detection | `10` cycle pattern (#4) | [005-redundant-connection.md](005-redundant-connection.md) | planned |
| 6 | Number of Operations to Make Network Connected | Medium | [LeetCode 1319](https://leetcode.com/problems/number-of-operations-to-make-network-connected/) | Components + spare edges | `10` components + cycle counting | [006-make-network-connected.md](006-make-network-connected.md) | planned |
| 7 | Satisfiability of Equality Equations | Medium | [LeetCode 990](https://leetcode.com/problems/satisfiability-of-equality-equations/) | Equivalence classes | `10` grouping pattern | [007-equality-equations.md](007-equality-equations.md) | planned |
| 8 | Smallest String With Swaps | Medium | [LeetCode 1202](https://leetcode.com/problems/smallest-string-with-swaps/) | Group then sort inside groups | `10` grouping + `02-arrays-and-strings` sorting | [008-smallest-string-with-swaps.md](008-smallest-string-with-swaps.md) | planned |
| 9 | Accounts Merge | Medium | [LeetCode 721](https://leetcode.com/problems/accounts-merge/) | Merging records by shared keys | `05-hashing` maps + `10` grouping | [009-accounts-merge.md](009-accounts-merge.md) | planned |
| 10 | Number of Islands (DSU variant) | Medium | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | Grid cells as DSU elements | `09-graphs` DFS version (ওখানে #4) | [010-number-of-islands-dsu.md](010-number-of-islands-dsu.md) | planned |
| 11 | Most Stones Removed with Same Row or Column | Medium | [LeetCode 947](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/) | Creative union keys (rows/cols as nodes) | `10` grouping pattern | [011-most-stones-removed.md](011-most-stones-removed.md) | planned |
| 12 | Regions Cut By Slashes | Medium | [LeetCode 959](https://leetcode.com/problems/regions-cut-by-slashes/) | Cell subdivision + union | `10` grid DSU (#10) | [012-regions-cut-by-slashes.md](012-regions-cut-by-slashes.md) | planned |
| 13 | Number of Islands II | Hard | [LeetCode 305](https://leetcode.com/problems/number-of-islands-ii/) | Streaming dynamic connectivity | `10` grid DSU (#10) — যে problem traversal পারে না | [013-number-of-islands-ii.md](013-number-of-islands-ii.md) | planned |
| 14 | Making A Large Island | Hard | [LeetCode 827](https://leetcode.com/problems/making-a-large-island/) | Component sizes + best merge | `10` size tracking | [014-making-a-large-island.md](014-making-a-large-island.md) | planned |
| 15 | Swim in Rising Water (DSU variant) | Hard | [LeetCode 778](https://leetcode.com/problems/swim-in-rising-water/) | Kruskal-style threshold union | `09-graphs` Dijkstra version (ওখানে #25) | [015-swim-in-rising-water-dsu.md](015-swim-in-rising-water-dsu.md) | planned |
| 16 | Redundant Connection II | Hard | [LeetCode 685](https://leetcode.com/problems/redundant-connection-ii/) | Directed cycle + double-parent cases | `10` cycle pattern (#5) | [016-redundant-connection-ii.md](016-redundant-connection-ii.md) | planned |
| 17 | Road Construction | Hard | [CSES 1676 · Road Construction](https://cses.fi/problemset/task/1676) | Live component count + max size | `10` size tracking, CP scale | [017-road-construction.md](017-road-construction.md) | planned |

## Suggested milestones

- **#3-এর পরে:** path compression + union by size — দুটো optimization চোখ বন্ধ করে লিখতে পারছ; basic DSU আয়ত্তে।
- **#7-এর পরে:** "এখানে কী union করছি?" প্রশ্নটা দেখলেই ধরতে পারছ; cycle detection আর component counting সহজ লাগছে।
- **#11-এর পরে:** row/column বা অন্য creative জিনিসকে DSU node বানানোর চোখ এসে গেছে — এটাই DSU-র আসল interview-শক্তি।
- **#14-এর পরে:** grid-কে DSU দিয়ে দেখা আর component size track করা রপ্ত; Hard variant গুলো আর ভয় লাগছে না।
- **সব ১৭টার পরে:** যে problem traversal দিয়ে কঠিন (streaming / dynamic connectivity), সেখানে DSU কেন স্বাভাবিক fit — নিজে বুঝিয়ে বলতে পারছ।

> আটকে গেলে আগে [../concept.md](../concept.md) আর [../visual-explanation.md](../visual-explanation.md)-এ ফিরে যাও — union/find-এর ছবিটা পরিষ্কার হলে বেশিরভাগ problem খুলে যায়।