016 — Redundant Connection II

Source

• Original source: Directed-graph rooted-tree restoration exercise
• Platform: LeetCode — https://leetcode.com/problems/redundant-connection-ii/
• 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 বলে দুটো আলাদা ভাঙন একসাথে সামলাতে হয়

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-টা দাও।

edges = [[1,2],[2,3],[3,1]]     (1->2->3->1, একটা directed cycle)
শেষ যে edge cycle বন্ধ করল  ->  [3,1]

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(α)।

6. Real-life analogy

ভাবো একটা কোম্পানির org-chart, যেখানে প্রত্যেকের ঠিক একজন boss থাকার কথা আর একদম উপরে এক CEO (যার boss নেই)। কেউ ভুল করে একটা বাড়তি reporting-line টেনেছে। দুটো গোলমাল হতে পারে — হয় একজনের দুজন boss দেখাচ্ছে, নয়তো একটা চক্র তৈরি হয়েছে (A রিপোর্ট করে B-কে, B করে A-কে, ঘুরেফিরে)। তোমাকে ঠিক একটা লাইন কাটতে হবে যাতে আবার পরিষ্কার গাছ-কাঠামো ফেরে — আর গোলমাল দুরকম থাকায় কোন লাইনটা কাটবে সেটাই আসল ধাঁধা।

7. Visual explanation

দুই phase: (1) double-parent খোঁজা (in-degree 2 node), (2) candidate বাদ রেখে DSU দিয়ে cycle খোঁজা।

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]

8. Example input and output

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]

9. Brute force thinking

সরল চিন্তা: প্রতিটা edge একে একে সরিয়ে দেখো — বাকি n−1 edge দিয়ে কি একটা বৈধ rooted tree হয় (ঠিক এক root, কোনো cycle নেই, সবাই reachable)? input-শেষ থেকে পেছন দিকে চেষ্টা করলে প্রথম যেটা কাজ করে সেটাই উত্তর।

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 আছে কি?" — এই প্রশ্নটাই আসল মোচড়।

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 ✓)

15. Python solution

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) সরালেই হয়।

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!।

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 ধরা পড়ে ভুল উত্তর আসে।

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-র "বারো লাইন"-এ, cycle demo "এক comparison-এ cycle detection"-এ।

22. Similar harder problems

• Redundant Connection (undirected, সহজ ভাই) — https://leetcode.com/problems/redundant-connection/ (এই tracker-এর #5)
• Graph Valid Tree (connectivity + cycle) — https://leetcode.com/problems/graph-valid-tree/ (#4)
• Course Schedule (directed cycle, traversal দিয়ে) — https://leetcode.com/problems/course-schedule/ (cross-ref ../../09-graphs/ topological sort)

23. Pattern learned

Directed cycle + double-parent cases: directed graph-এ "একটা edge সরিয়ে বৈধ rooted tree ফেরাও" — দুই উপসর্গ আলাদা করে ভাবো: কোনো node-এর in-degree 2 (double-parent) আর/অথবা cycle। double-parent থাকলে দুই candidate; পরেরটা বাদ রেখে DSU চালিয়ে cycle থাকা/না-থাকা দেখে আগের/পরের বেছে নাও। double-parent না থাকলে সাধারণ DSU cycle-edge।

24. Final summary

ভবিষ্যতের আমাকে: redundant-edge problem-এ আগে দেখো edge directed না undirected। undirected হলে #5-এর সরল DSU। directed হলে দুই ধাপ — double-parent খোঁজো, তারপর candidate বাদ রেখে cycle-test করে তিন case (cycle-only / double-only / both) আলাদা করো। "double-parent আছে কি?" — এই প্রশ্নই পুরো সমাধানের দিক ঠিক করে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।