Problem link ও উৎস
- **Original source:** Classic dynamic-connectivity exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Easy
- **Pattern:** dynamic connectivity (same group?)
- **Basic idea inherited from:** [../../09-graphs/](../../09-graphs/README.md)-এর একই problem-এর BFS version; এখানে আমরা path খুঁজি না, শুধু "একই component কিনা" জিজ্ঞেস করি
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা node (0 থেকে n−1) আর কতগুলো undirected edge দেওয়া আছে। তোমাকে বলতে হবে — `source` থেকে `destination`-এ যাওয়ার কোনো path আছে কি না। শুধু হ্যাঁ/না; আসল রাস্তাটা কেমন তা জানতে চাওয়া হয়নি।
```text
n = 6
edges = (0-1) (0-2) (3-5) (5-4) (4-3)
source = 0, destination = 5 -> path নেই? না! (False)
source = 0, destination = 2 -> path আছে? হ্যাঁ! (True)
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=3, edges=[[0,1],[1,2],[2,0]], source=0, destination=2
Output: True
Input : n=6, edges=[[0,1],[0,2],[3,5],[5,4],[4,3]], source=0, destination=5
Output: False
Edge case (একই node): n=1, edges=[], source=0, destination=0 -> True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বিশাল party, যেখানে friend circle গুলো পরিচয় হতে হতে মিশে যাচ্ছে (concept.md-র সেই party)। তুমি জানতে চাও — "Alice আর Frank কি একই circle-এ?" তুমি পুরো ঘর খুঁজে বেড়াও না; দুজনকেই জিজ্ঞেস করো "তোমার circle-এর spokesperson কে?" একই spokesperson হলে একই circle। Spokesperson = representative।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **"দুটো node কি একই connected component-এ?"** — এটাই DSU-র জন্মগত প্রশ্ন। [../../09-graphs/](../../09-graphs/README.md)-এ তুমি এই same problem BFS দিয়ে solve করেছ: source থেকে হেঁটে দেখেছ destination ছোঁয়া যায় কি না। DSU সেই হাঁটাটা বাদ দিয়ে শুধু **representative** মেলায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **equivalence relation**: "connected" সম্পর্কটা reflexive (নিজে নিজের সাথে যুক্ত), symmetric (undirected), আর transitive (a–b আর b–c যুক্ত হলে a–c যুক্ত)। এমন relation মানেই node-গুলো ভাগ হয়ে যায় কতগুলো **disjoint equivalence class**-এ — যেগুলোই connected components। দুটো node একই class-এ থাকলেই path আছে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **Disjoint Set Union (union–find)** — দুটো integer array: `parent` (কে কাকে point করে) আর `size` (প্রতি group কত বড়)। কোনো adjacency list রাখার দরকারই নেই; edge গুলো শুধু union করার কাঁচামাল।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা path নয়, শুধু **membership** — "same group?"। DSU ঠিক এই দুটো কাজই near-constant time-এ করে: `union` দিয়ে দুই group জোড়া, `find` দিয়ে representative বের করা। Path বা distance DSU মনে রাখে না, কিন্তু এখানে সেসব লাগেও না — তাই এটাই সবচেয়ে হালকা fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: adjacency list বানাও, তারপর source থেকে BFS বা DFS চালাও; destination ছুঁলে True, queue/stack ফুরিয়ে গেলে False।
```text
1) প্রতিটা edge -> adjacency list-এ যোগ করো
2) source থেকে BFS শুরু করো
3) destination পেলে থামো -> True; না পেলে -> False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
একটা মাত্র query-র জন্য BFS ঠিকঠাক — O(V + E)। কিন্তু যদি **অনেক** (source, destination) query আসত, অথবা edge গুলো **একটা একটা করে আসত আর মাঝে মাঝে query ঢুকত** (dynamic connectivity), তখন প্রতিবার পুরো graph নতুন করে চষা অপচয়। BFS query-র মাঝে কিছু মনে রাখে না; DSU মনে রাখে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **আসল রাস্তাটা অপ্রাসঙ্গিক।** আমাদের শুধু জানা দরকার দুটো node একই group-এ কি না। তাই edge-গুলোকে relation হিসেবে গুঁড়িয়ে disjoint set-এ ভেঙে ফেলো; query হয়ে যায় দুটো `find`-এর তুলনা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব edge `union` করে component গড়ে নাও — এটা একবারের কাজ। তারপর `find(source) == find(destination)` দিয়ে উত্তর দাও। Path compression + union by size থাকায় প্রতিটা operation amortized প্রায় constant — এত fast যে interview-তে α(n)-কে নির্দ্বিধায় "≈ O(1)" ধরতে পারো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "source থেকে destination-এ কীভাবে পৌঁছব?" — এই হাঁটার চিন্তাটা ছেড়ে দাও। বদলে জিজ্ঞেস করো "ওরা কি একই দলের?" পথের প্রশ্নকে দলের প্রশ্নে অনুবাদ করলেই DSU দরজা খুলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা edge-কে union হিসেবে খাওয়াও; forest গড়ে ওঠে। তারপর দুটো `find` মেলাও।
```text
edges: (0-1) (0-2) (3-5) (5-4)
শুরু: *0 *1 *2 *3 *4 *5 parent: [0,1,2,3,4,5]
union(0,1): *0 *2 *3 *4 *5
|
1 parent: [0,0,2,3,4,5]
union(0,2): *0 *3 *4 *5
/ \
1 2 parent: [0,0,0,3,4,5]
union(3,5): *0 *3 *4
/ \ |
1 2 5 parent: [0,0,0,3,4,3]
union(5,4): *0 *3
/ \ / \
1 2 5 4 parent: [0,0,0,3,4,3] (4 hangs under 3)
প্রশ্ন: path(0, 5)? find(0)=0, find(5)=3 -> 0 != 3 -> False
প্রশ্ন: path(0, 2)? find(0)=0, find(2)=0 -> 0 == 0 -> True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `n=6, edges=[[0,1],[0,2],[3,5],[5,4]], source=0, destination=5`:
1. `union(0,1)` → roots 0,1 আলাদা; `parent[1]=0`, size[0]=2 → component {0,1}
2. `union(0,2)` → find(0)=0, find(2)=2; `parent[2]=0`, size[0]=3 → {0,1,2}
3. `union(3,5)` → `parent[5]=3`, size[3]=2 → {3,5}
4. `union(5,4)` → find(5)=3, find(4)=4; size[3]=2>1, `parent[4]=3` → {3,5,4}
5. query: `find(0)=0`, `find(5)=3` → `0 != 3` → **False**
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n # প্রতিটা group-এ একজন
def find(self, x): # representative + path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, x, y): # union by size; merge হলে True
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # আগে থেকেই এক group
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx # rx এখন বড় root
self.parent[ry] = rx # ছোটটা বড়টার নিচে ঝোলে
self.size[rx] += self.size[ry]
return True
def valid_path(n, edges, source, destination):
dsu = DSU(n)
for u, v in edges:
dsu.union(u, v) # সব edge দিয়ে component গড়ো
return dsu.find(source) == dsu.find(destination)
# ---- tests ----
assert valid_path(3, [[0, 1], [1, 2], [2, 0]], 0, 2) is True
assert valid_path(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5) is False
assert valid_path(1, [], 0, 0) is True # একই node
assert valid_path(2, [], 0, 1) is False # কোনো edge নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `parent = list(range(n))` — শুরুতে প্রত্যেকে নিজের root, মানে n টা আলাদা group।
- `find` — root-এ ওঠার পথে প্রতিটা node-কে grandparent-এ re-point করে (path halving), তাই পরের বার হাঁটা ছোট।
- `union` — দুই root আলাদা হলে ছোট tree-টা বড়টার নিচে ঝোলায়; সমান হলে আগে থেকেই এক group, `False` ফেরায়।
- `for u, v in edges: dsu.union(u, v)` — সব connection গিলে component তৈরি।
- `return dsu.find(source) == dsu.find(destination)` — একই representative মানেই path আছে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ triangle 0-1-2 এক component, তাই path(0,2) True। দ্বিতীয়টায় {0,1,2} আর {3,4,5} দুটো আলাদা দ্বীপ, তাই path(0,5) False। তৃতীয়টায় source==destination, find একই — True। চতুর্থটায় edge নেই, 0 আর 1 আলাদা — False। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O((V + E) · α(V))** ≈ **O(V + E)** — প্রতিটা edge একটা `union`, query দুটো `find`; প্রতিটা operation amortized near-constant (inverse Ackermann, যা বাস্তবে ≤ 4)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V)** — শুধু `parent` আর `size` array; adjacency list রাখাই লাগে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `find(source) == find(destination)`-এর বদলে `parent[source] == parent[destination]` compare করা — tree flat না হলে parent ≠ representative; এটাই classic DSU bug।
- DSU array-র size `n`-এর বদলে edge-সংখ্যা দিয়ে নেওয়া।
- source == destination edge case ভুলে যাওয়া (এখানে এমনিতেই True আসে, কারণ একই index-এর find একই)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../09-graphs/](../../09-graphs/README.md)-এর connectivity / "path exists" BFS। ওখানে তুমি queue দিয়ে হেঁটেছিলে; এখানে union/find দিয়ে group মিলিয়েছ। একটামাত্র static query-তে দুটোই O(V+E); কিন্তু query স্রোতের মতো এলে DSU এগিয়ে। DSU-র মূল snippet [../concept.md](../concept.md)-র "বারো লাইন"-এ আছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Provinces (component গোনা) —