Disjoint Set Union — Problem Tracker¶
এই folder DSU-র practice problems track করে। প্রতিটা problem তার নিজের একটা note file পায় (Note file column-এ নাম দেওয়া), যা ../../templates/ds-problem-note-template.md-এর 24-section template দিয়ে লেখা — analogy, pattern, thinking tweak, dry run, complexity, mistakes, আর বাকি সব। List-টা easy থেকে hard-এ সাজানো; কয়েকটা problem ইচ্ছে করে ../../09-graphs/ থেকে repeat করা, যাতে তুমি DSU solution-টা তোমার traversal solution-এর পাশে লিখে তুলনা করতে পারো।
এই tracker কীভাবে ব্যবহার করবে:
- link দিয়ে official statement পড়ো (main
../README.mdpractice list-এও আছে)। - code করার আগে দুটো প্রশ্নের উত্তর লিখে দাও: আমি কী union করছি? আর সাথে কোন extra data চড়তে হবে (sizes, counts)? বেশিরভাগ DSU problem ওই উত্তরগুলো ঠিক হওয়ার মুহূর্তেই solve হয়ে যায়।
- কিছু দেখার আগে অন্তত 25 মিনিট চেষ্টা করো।
- 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 | Dynamic connectivity | 09-graphs একই problem-এর BFS version |
001-find-if-path-exists-dsu.md | planned |
| 2 | Number of Provinces | Easy-Medium | LeetCode 547 | Component counting | 09-graphs DFS version (ওখানে #6) |
002-number-of-provinces-dsu.md | planned |
| 3 | Building Roads | Easy | CSES task 1666 | Components − 1 | 09-graphs components |
003-building-roads-dsu.md | planned |
| 4 | Graph Valid Tree | Medium | LeetCode 261 | Cycle detection + count | 10 union returns False insight |
004-graph-valid-tree.md | planned |
| 5 | Redundant Connection | Medium | LeetCode 684 | Cycle detection | 10 cycle pattern (#4) |
005-redundant-connection.md | planned |
| 6 | Number of Operations to Make Network Connected | Medium | LeetCode 1319 | Components + spare edges | 10 components + cycle counting |
006-make-network-connected.md | planned |
| 7 | Satisfiability of Equality Equations | Medium | LeetCode 990 | Equivalence classes | 10 grouping pattern |
007-equality-equations.md | planned |
| 8 | Smallest String With Swaps | Medium | LeetCode 1202 | Group then sort inside groups | 10 grouping + 02-arrays-and-strings sorting |
008-smallest-string-with-swaps.md | planned |
| 9 | Accounts Merge | Medium | LeetCode 721 | Merging records by shared keys | 05-hashing maps + 10 grouping |
009-accounts-merge.md | planned |
| 10 | Number of Islands (DSU variant) | Medium | LeetCode 200 | Grid cells as DSU elements | 09-graphs DFS version (ওখানে #4) |
010-number-of-islands-dsu.md | planned |
| 11 | Most Stones Removed with Same Row or Column | Medium | LeetCode 947 | Creative union keys (rows/cols as nodes) | 10 grouping pattern |
011-most-stones-removed.md | planned |
| 12 | Regions Cut By Slashes | Medium | LeetCode 959 | Cell subdivision + union | 10 grid DSU (#10) |
012-regions-cut-by-slashes.md | planned |
| 13 | Number of Islands II | Hard | LeetCode 305 | Streaming dynamic connectivity | 10 grid DSU (#10) — যে problem traversal পারে না |
013-number-of-islands-ii.md | planned |
| 14 | Making A Large Island | Hard | LeetCode 827 | Component sizes + best merge | 10 size tracking |
014-making-a-large-island.md | planned |
| 15 | Swim in Rising Water (DSU variant) | Hard | LeetCode 778 | Kruskal-style threshold union | 09-graphs Dijkstra version (ওখানে #25) |
015-swim-in-rising-water-dsu.md | planned |
| 16 | Redundant Connection II | Hard | LeetCode 685 | Directed cycle + double-parent cases | 10 cycle pattern (#5) |
016-redundant-connection-ii.md | planned |
| 17 | Road Construction | Hard | CSES Problem Set — "Road Construction" | Live component count + max size | 10 size tracking, CP scale |
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 আর ../visual-explanation.md-এ ফিরে যাও — union/find-এর ছবিটা পরিষ্কার হলে বেশিরভাগ problem খুলে যায়।