Problem link ও উৎস
- **Original source:** Classic tree-validation exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** cycle detection + component count
- **Basic idea inherited from:** `10`-এর "union False ফেরালে cycle" insight; এখানে দুটো শর্ত একসাথে — শূন্য cycle আর সব node এক component
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা node (0 থেকে n−1) আর কতগুলো undirected edge দেওয়া। তোমাকে বলতে হবে — এই edge-গুলো মিলে একটা **valid tree** বানায় কি না। Tree মানে: সব node যুক্ত (একটাই component) আর কোথাও কোনো cycle নেই।
```text
n = 5
edges = (0-1) (0-2) (0-3) (1-4) -> সব যুক্ত, cycle নেই -> True
n = 5
edges = (0-1) (1-2) (2-3) (1-3) (1-4) -> 1-2-3-1 একটা cycle -> False
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
Output: True
Input : n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: False (cycle 1-2-3-1)
Edge case (disconnected): n=4, edges=[[0,1],[2,3]] -> False (দুই component)
Edge case (single node) : n=1, edges=[] -> True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
party-র friend circle আবার, তবে এবার একটা নিয়ম: তুমি একটা **নিখুঁত পরিচয়-শৃঙ্খল** চাও যেখানে সবাই শেষমেশ এক circle-এ, কিন্তু কোনো দুজন **দুবার** পরিচিত হয়নি। যদি দুজন আগে-পরিচিত মানুষ আবার হাত মেলায়, সেটা একটা অপচয়ী লুপ (cycle)। আর শেষে যদি একাধিক circle টিকে থাকে, সবাই যুক্ত হয়নি। দুটোর একটাও ঘটলে — এটা "valid tree" নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **concept.md-র cycle guard** — undirected graph-এ `union` যখন দুটো **already-connected** node-এ চলে, তখন সেই edge একটা cycle বন্ধ করে, আর `union` `False` ফেরায়। এই একটামাত্র insight দিয়ে cycle ধরা পড়ে। সাথে জুড়ে দাও component counting (#2), তাহলেই tree-র দুটো শর্ত হাতের মুঠোয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা পরিষ্কার গাণিতিক fact: **n-node tree-র ঠিক n−1 edge থাকে, না বেশি না কম।** এর থেকে একটা সুন্দর shortcut আসে — edge-সংখ্যা ঠিক `n−1` না হলে আগেই `False`। আর যদি ঠিক `n−1` edge থাকে এবং কোনো cycle না থাকে, তাহলে graph স্বয়ংক্রিয়ভাবেই connected (n−1 edge দিয়ে cycle ছাড়া n node যোগ করার একমাত্র উপায়)। তাই দুটো check যথেষ্ট: edge গোনা + cycle না থাকা।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`parent` + `size` array)। কোনো adjacency list বা recursion লাগে না — edge-গুলোকে শুধু `union`-এর কাঁচামাল হিসেবে খাওয়াই, আর কোনো `union` `False` ফেরায় কি না সেটা দেখি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা "tree কি না" — মানে connectivity + cycle, ঠিক DSU-র জন্মগত দুটো প্রশ্ন। `union`-এর return value একই সাথে merge করে আর cycle ধরিয়ে দেয়, তাই আলাদা DFS coloring বা visited bookkeeping লাগে না। Path বা distance এখানে অপ্রাসঙ্গিক, তাই DSU-ই সবচেয়ে হালকা fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: adjacency list বানাও, একটা `visited` set রাখো, parent মনে রেখে DFS চালাও; DFS-এ parent ছাড়া অন্য কোনো visited node-এ গেলে cycle। শেষে visited-এর সংখ্যা `n` কি না দেখে connectivity যাচাই করো।
```text
1) adjacency list বানাও
2) node 0 থেকে DFS, parent track করো
3) parent ছাড়া visited প্রতিবেশী পেলে -> cycle -> False
4) DFS শেষে visited == n না হলে -> disconnected -> False
5) দুটো check টিকলে -> True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
DFS version O(V + E), যা ঠিকঠাক — কিন্তু এতে adjacency list গড়া, recursion stack, parent-tracking, আর শেষে আলাদা connectivity check লাগে; cycle আর connectivity দুটো ভিন্ন logic। DSU একই O(E·α) খরচে দুটোকেই এক `union`-return-এ মিলিয়ে দেয়, কোনো recursion বা adjacency ছাড়াই — code ছোট, ভুলের জায়গা কম।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **tree = শূন্য cycle + এক component**, আর এর একটা চমৎকার সংক্ষিপ্ত রূপ আছে — **ঠিক n−1 edge আর শূন্য cycle**। edge-সংখ্যা আগে গুনে নিলে, n−1 না হলেই তাড়াতাড়ি `False`; n−1 হলে শুধু cycle না-থাকা যাচাই করলেই connectivity নিশ্চিত।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে `len(edges) != n-1` হলে সরাসরি `False`। নাহলে সব edge `union` করো; কোনো `union` `False` ফেরালে cycle ⇒ `False`। সব edge সফলভাবে merge হলে ⇒ `True`। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "DFS দিয়ে cycle খুঁজি, আবার আলাদা করে connectivity দেখি" — এই দুই-ধাপের চিন্তা ছাড়ো। বদলে ভাবো "n−1 edge গুনে নিই, তারপর একটাও cycle আছে কি না দেখি — না থাকলেই tree।" Edge-গোনা শর্তটাই connectivity-র কাজটা বিনামূল্যে করে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা edge union করো; কোনো `union` False ফেরালে cycle ⇒ False। Loop শেষে component একটার বেশি থাকলেও False।
```text
n = 5, edges: (0-1) (0-2) (0-3) (1-4) [4 edges == n-1, ভালো লক্ষণ]
শুরু: *0 *1 *2 *3 *4 parent: [0,1,2,3,4]
union(0,1): *0 *2 *3 *4
|
1 parent: [0,0,2,3,4]
union(0,2): *0 *3 *4
/ \
1 2 parent: [0,0,0,3,4]
union(0,3): *0 *4
/ | \
1 2 3 parent: [0,0,0,0,4]
union(1,4): find(1)=0, find(4)=4 -> merge
*0
/ | | \
1 2 3 4 parent: [0,0,0,0,0] এক component, কোনো False -> True
------ cycle case: edges (0-1)(1-2)(2-0) ------
union(0,1) ok ; union(1,2) ok ; union(2,0): find(2)=0, find(0)=0 -> False (cycle!) -> not a tree
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `n=5, edges=[[0,1],[0,2],[0,3],[1,4]]`:
1. edge-সংখ্যা = 4 = n−1 → শুরুর check পাস
2. `union(0,1)` → roots আলাদা, merge সফল → {0,1}
3. `union(0,2)` → merge সফল → {0,1,2}
4. `union(0,3)` → merge সফল → {0,1,2,3}
5. `union(1,4)` → find(1)=0, find(4)=4, merge সফল → {0,1,2,3,4}
6. কোনো `union` `False` ফেরায়নি → cycle নেই → return **True**
## কোড ও ব্যাখ্যা {#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 -> cycle
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_tree(n, edges):
if len(edges) != n - 1: # tree-র ঠিক n-1 edge লাগে
return False
dsu = DSU(n)
for u, v in edges:
if not dsu.union(u, v): # False -> দুটো node আগেই যুক্ত -> cycle
return False
return True # n-1 edge + শূন্য cycle -> tree
# ---- tests ----
assert valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
assert valid_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
assert valid_tree(4, [[0, 1], [2, 3]]) is False # disconnected
assert valid_tree(1, []) is True # একটাই node
assert valid_tree(2, [[0, 1]]) is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if len(edges) != n - 1: return False` — tree-র edge-সংখ্যা ঠিক n−1; এই এক লাইন একসাথে "too many edges" (cycle অনিবার্য) আর "too few" (disconnect অনিবার্য) দুটোই ছেঁকে ফেলে।
- `for u, v in edges: if not dsu.union(u, v)` — প্রতিটা edge merge করার চেষ্টা; `union` `False` মানে u আর v আগেই এক group, অর্থাৎ এই edge একটা cycle বন্ধ করছে।
- `return False` (loop-এর ভেতরে) — cycle পাওয়া গেছে, আর tree হতে পারে না।
- `return True` — n−1 edge সফলভাবে merge হয়েছে, কোনো cycle নেই; edge-count শর্ত connectivity নিশ্চিত করে, তাই এটাই tree।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ 4 edge (= n−1) সব সফল merge — cycle নেই, True। দ্বিতীয়টায় 5 edge কিন্তু n−1 = 4, তাই edge-count check-এই False (এ ছাড়াও 1-2-3-1 cycle আছে)। তৃতীয়টায় 2 edge কিন্তু n−1 = 3, edge-count মেলে না — False (disconnected)। single-node case-এ 0 edge = n−1, True। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(E · α(V))** ≈ **O(V)** — edge-count check O(1); তারপর প্রতিটা edge একটা `union`, প্রতিটা amortized near-constant (inverse Ackermann, বাস্তবে ≤ 4)। যেহেতু valid হলে E = V−1, খরচ কার্যত O(V)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V)** — শুধু `parent` আর `size` array; কোনো adjacency list বা recursion stack নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- edge-count shortcut ভুলে গিয়ে শুধু cycle check করা — তখন disconnected case (দুই আলাদা tree) ভুল করে `True` ফেরে; connectivity আলাদা করে যাচাই করতে হতো।
- `union`-এর `False` return ব্যবহার না করে আলাদা DFS দিয়ে cycle খোঁজা — কাজ করে, কিন্তু অহেতুক জটিল।
- DSU array-র size `n`-এর বদলে edge-সংখ্যা দিয়ে নেওয়া।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: এই tracker-এর DSU cycle-detection insight (concept.md-র "union False ফেরালে cycle")। মূল gap-filling fact — "tree + ঠিক একটা extra edge = ঠিক একটা cycle" — [../../09-graphs/concept.md](../../09-graphs/concept.md)-তেও আছে। DFS দিয়েও tree যাচাই করা যায় (parent-tracking + visited count); graph fixed আর একবার দেখলে DFS সমান fast, কিন্তু DSU-র code ছোট আর cycle+connectivity এক জায়গায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Redundant Connection (cycle বন্ধ করা edge-টা ফেরত দাও) —