Problem link ও উৎস
- **Original source:** Directed-graph rooted-tree restoration exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Hard
- **Pattern:** directed cycle + double-parent cases (rooted tree-তে কোন edge সরালে ঠিক হয়)
- **Basic idea inherited from:** `10`-এর cycle pattern (#5 Redundant Connection); এখানে edge directed বলে দুটো আলাদা ভাঙন একসাথে সামলাতে হয়
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা rooted tree-তে (যেখানে root-এর কোনো parent নেই, বাকি প্রতিটা node-এর ঠিক একটা parent) একটা extra directed edge যোগ করা হয়েছে — ফলে `n` node, `n` directed edge। তোমাকে সেই **একটা** extra edge বের করতে হবে, যেটা সরালে আবার বৈধ rooted tree পাওয়া যায়। একাধিক উত্তর সম্ভব হলে input-এ **শেষে আসা** edge-টা দাও।
```text
edges = [[1,2],[2,3],[3,1]] (1->2->3->1, একটা directed cycle)
শেষ যে edge cycle বন্ধ করল -> [3,1]
```
### Input ও output {#8-example-input-and-output}
```text
Input : edges=[[1,2],[2,3],[3,4],[4,1],[1,5]] Output: [4,1] (শুধু cycle)
Input : edges=[[1,2],[1,3],[2,3]] Output: [2,3] (double-parent, no cycle)
Input : edges=[[1,2],[2,3],[3,1],[1,4],[4,3]] Output: [2,3] (double-parent + cycle)
Edge : edges=[[1,2],[2,3],[3,1]] -> simple 3-cycle -> [3,1]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা কোম্পানির org-chart, যেখানে প্রত্যেকের ঠিক একজন boss থাকার কথা আর একদম উপরে এক CEO (যার boss নেই)। কেউ ভুল করে একটা বাড়তি reporting-line টেনেছে। দুটো গোলমাল হতে পারে — হয় একজনের **দুজন boss** দেখাচ্ছে, নয়তো একটা **চক্র** তৈরি হয়েছে (A রিপোর্ট করে B-কে, B করে A-কে, ঘুরেফিরে)। তোমাকে ঠিক একটা লাইন কাটতে হবে যাতে আবার পরিষ্কার গাছ-কাঠামো ফেরে — আর গোলমাল দুরকম থাকায় কোন লাইনটা কাটবে সেটাই আসল ধাঁধা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি `10`-এর #5 (Redundant Connection) — undirected graph-এ DSU দিয়ে cycle-closing edge ধরা। কিন্তু এখানে edge **directed**, তাই দুটো আলাদা ভাঙন হতে পারে: (a) কোনো node-এর **দুই parent** (in-degree 2), অথবা (b) একটা **directed cycle**। কখনো দুটোই একসাথে — সেটাই Hard করে তোলে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা বৈধ rooted tree-তে ঠিক এক root (in-degree 0), বাকি সবার in-degree 1, আর কোনো cycle নেই। একটা extra edge ঠিক তিন ভাবে ভাঙে:
- **Case 1 — শুধু cycle, double-parent নেই:** cycle বন্ধ-করা শেষ edge সরাও।
- **Case 2 — double-parent, cycle নেই:** যে দুই edge একই node-এ ঢোকে, তার মধ্যে **পরেরটা** সরাও।
- **Case 3 — double-parent + cycle:** double-parent দুই candidate-এর মধ্যে যেটা সরালে cycle-ও ভাঙে (সাধারণত **আগেরটা**) সেটাই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`n+1` element, 1-indexed) cycle ধরতে; আর একটা `parent[v]` array node-এর graph-parent track করতে (double-parent detect)। দুটো candidate edge রাখার দুটো ভেরিয়েবল।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
cycle detection-এ DSU-র `union`-এর False-return ঠিক সেই সংকেত — কোনো DFS coloring লাগে না (#5-এর মতোই)। directed হওয়ায় তার আগে আমরা শুধু double-parent খুঁজি (একটা array দিয়ে), আর সেই candidate-কে আপাতত বাদ রেখে বাকিটা undirected-এর মতো DSU-তে গিলি। দুই tool একসাথে তিনটে case সামলে দেয়, প্রতিটা O(α)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা edge একে একে সরিয়ে দেখো — বাকি `n−1` edge দিয়ে কি একটা বৈধ rooted tree হয় (ঠিক এক root, কোনো cycle নেই, সবাই reachable)? input-শেষ থেকে পেছন দিকে চেষ্টা করলে প্রথম যেটা কাজ করে সেটাই উত্তর।
```text
1) edges শেষ থেকে শুরুর দিকে প্রতিটা edge e:
2) e বাদ দিয়ে graph বানাও
3) এটা কি বৈধ rooted tree? (cycle নেই, এক root)
4) হ্যাঁ হলে -> উত্তর e
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা edge সরিয়ে পুরো validity check — `O(n)` প্রতি edge, `n` edge → `O(n²)`। ছোট input-এ চলে, কিন্তু অপ্রয়োজনীয়: double-parent কিনা একটা scan-এ ধরা যায়, আর cycle DSU দিয়ে এক pass-এ। সঠিক case-analysis করলে পুরোটা `O(n · α(n))` ≈ linear।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **directed redundant-edge ঠিক তিন রকম, আর double-parent ও cycle — এই দুই উপসর্গ দিয়েই কোন case তা ঠিক হয়।** যদি কোনো node-এর দুই parent থাকে, তবে দুই সন্দেহভাজন edge। তার মধ্যে পরেরটাকে বাদ রেখে DSU চালাও: এখনো cycle থাকলে দোষ আগেরটার (cand1), নইলে পরেরটা (cand2)। double-parent না থাকলে DSU-র প্রথম cycle-edge-ই উত্তর।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Phase 1: প্রতিটা edge `(u,v)` দেখে `parent[v]` track করো; কোনো `v`-তে দ্বিতীয় parent পেলে `cand1` = আগের edge, `cand2` = এখনকার edge, আর `cand2`-কে skip-mark করো। Phase 2: skip বাদে সব edge DSU-তে union। union False (cycle) এলে — `cand1` থাকলে answer `cand1` (case 3), নইলে current edge (case 1)। loop শেষেও cycle না এলে answer `cand2` (case 2)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** undirected #5-এর মতো "শুধু প্রথম cycle-edge" ভেবো না — directed-এ আগে দেখো **কোনো node-এর কি দুই parent?** যদি থাকে, সেই দুই edge-ই প্রধান সন্দেহভাজন; পরেরটা বাদ রেখে cycle থাকে কিনা দেখে আগের/পরের বেছে নাও। "double-parent আছে কি?" — এই প্রশ্নটাই আসল মোচড়।
### ছবিতে বোঝা {#7-visual-explanation}
দুই phase: (1) double-parent খোঁজা (in-degree 2 node), (2) candidate বাদ রেখে DSU দিয়ে cycle খোঁজা।
```text
Case 1 — শুধু cycle:
1 -> 2 -> 3 -> 1 double-parent নেই
DSU-তে edge গিলতে গিলতে [3->1] union False -> cycle
উত্তর = শেষ cycle-edge = [3,1]
Case 2 — double-parent, cycle নেই:
1 -> 2 node 3-এর দুই parent: 1 আর 2
1 -> 3 cand1=[1,3] (আগের), cand2=[2,3] (পরের)
2 -> 3 cand2 বাদ রেখে DSU -> cycle নেই -> উত্তর = cand2 = [2,3]
Case 3 — double-parent + cycle:
1 -> 2 node 3-এর দুই parent: 2 আর 4
2 -> 3 cand1=[2,3] (আগের), cand2=[4,3] (পরের)
3 -> 1 cand2 বাদ রাখলেও 1->2->3->1 cycle থাকে!
1 -> 4 cycle মানে cand2 সরালে চলবে না
4 -> 3 -> উত্তর = cand1 = [2,3]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `edges=[[1,2],[2,3],[3,1],[1,4],[4,3]]` (Case 3):
1. Phase 1: `parent[2]=1`, `parent[3]=2`, `parent[1]=3`, `parent[4]=1`। edge `[4,3]`-এ `parent[3]` আগেই 2 → double-parent। `cand1=[2,3]`, `cand2=[4,3]`, skip = index 4
2. Phase 2: `[1,2]` union ok; `[2,3]` union ok; `[3,1]` union → find(3)=find(1)? রুট মিলে → **False (cycle)**
3. cycle পেলাম আর `cand1` আছে → answer `cand1` = **[2,3]**
4. (যাচাই: `[2,3]` সরালে `1→2, 4→3, 3→1, 1→4` — cycle নেই, এক root; বৈধ tree ✓)
## কোড ও ব্যাখ্যা {#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 find_redundant_directed(edges):
n = len(edges)
parent = [0] * (n + 1) # node -> তার একমাত্র graph-parent
skip = -1 # যে edge index আপাতত বাদ (cand2)
cand1 = cand2 = None
# Phase 1: double-parent খোঁজো
for i, (u, v) in enumerate(edges):
if parent[v] != 0: # v-র আগেই একটা parent আছে
cand1 = [parent[v], v] # আগের edge
cand2 = [u, v] # এখনকার edge
skip = i # cand2-কে আপাতত বাদ রাখি
else:
parent[v] = u
# Phase 2: cand2 বাদ রেখে DSU দিয়ে cycle খোঁজো
dsu = DSU(n + 1)
for i, (u, v) in enumerate(edges):
if i == skip: # বাদ-রাখা edge — skip
continue
if not dsu.union(u, v): # cycle পাওয়া গেল
if cand1 is None:
return [u, v] # double-parent নেই -> এই edge-ই উত্তর (case 1)
return cand1 # double-parent আছে -> আগেরটা সরাও (case 3)
return cand2 # cycle নেই -> বাদ-রাখা edge-ই উত্তর (case 2)
# ---- tests ----
assert find_redundant_directed([[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]) == [4, 1] # case 1
assert find_redundant_directed([[1, 2], [1, 3], [2, 3]]) == [2, 3] # case 2
assert find_redundant_directed([[1, 2], [2, 3], [3, 1], [1, 4], [4, 3]]) == [2, 3] # case 3
assert find_redundant_directed([[1, 2], [2, 3], [3, 1]]) == [3, 1] # simple cycle
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `parent[v]` array — graph-parent (DSU-র parent নয়); `parent[v] != 0` মানে `v`-র আগেই একটা parent আছে → double-parent।
- `cand1` / `cand2` / `skip` — double-parent পেলে আগের ও পরের edge মনে রাখি, পরেরটা (cand2) Phase 2-এ বাদ রাখি।
- Phase 2-এর `dsu.union` — cand2 বাদ রেখে বাকি edge union; এখানে cycle থাকা মানে cand2 সরালেও সমস্যা থেকে যায়।
- `if not dsu.union(...)` — False = cycle; `cand1` থাকলে case 3 (আগের সরাও), না থাকলে case 1 (এই cycle-edge)।
- `return cand2` — Phase 2-এ cycle না পেলে double-parent-ই একমাত্র সমস্যা ছিল; পরের edge (cand2) সরালেই হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
test 1 (case 1): double-parent নেই, DSU-তে `[4,1]` cycle বন্ধ করে → `[4,1]`। test 2 (case 2): node 3-এর দুই parent, cand2 `[2,3]` বাদ দিলে cycle নেই → `[2,3]`। test 3 (case 3): cand2 `[4,3]` বাদ দিলেও 1-2-3-1 cycle থাকে → আগের cand1 `[2,3]`। test 4: simple 3-cycle, `[3,1]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · α(n))** ≈ **O(n)** — Phase 1 একটা linear scan, Phase 2 প্রতিটা edge একটা union/find amortized near-constant।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `parent` array, DSU-র `parent`+`size` array; candidate ভেরিয়েবল O(1)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- directed-কে undirected ভেবে শুধু #5-এর মতো প্রথম cycle-edge ফেরানো — double-parent case ধরা পড়ে না।
- double-parent পেলে cand1 না cand2 — কোনটা সরাবে গুলিয়ে ফেলা; নিয়ম: cand2 বাদ রেখে cycle থাকলে cand1, নইলে cand2।
- DSU array `n`-এর বদলে `n+1` না নেওয়া (1-indexed node, তাই index 0 খালি রেখে `n+1`)।
- skip-edge-কে DSU-তে গিলে ফেলা — তাহলে double-parent থেকেই cycle ধরা পড়ে ভুল উত্তর আসে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: `10`-এর #5 Redundant Connection (undirected cycle, DSU-False = cycle)। এখানে directed হওয়ায় তার আগে double-parent detection যোগ হয়, আর cycle-test দিয়ে তিন case আলাদা করা হয়। মূল cycle-trick অপরিবর্তিত — `union` False-ই detector। DSU snippet [../concept.md](../concept.md)-র "বারো লাইন"-এ, cycle demo "এক comparison-এ cycle detection"-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Redundant Connection (undirected, সহজ ভাই) —