005 — Redundant Connection

Source

• Original source: Classic cycle-edge exercise
• Platform: LeetCode — https://leetcode.com/problems/redundant-connection/
• Topic: disjoint set union
• Difficulty: Medium
• Pattern: cycle detection
• Basic idea inherited from: 10-এর cycle pattern (#4); এখানে শুধু cycle ধরাই নয়, কোন edge cycle বন্ধ করল সেটাও ফেরত দিতে হয়

1. Problem in simple words

একটা graph শুরু হয়েছিল tree হিসেবে (n টা node, n−1 edge), তারপর একটা বাড়তি edge যোগ করা হয়েছে — ফলে মোট n edge আর ঠিক একটা cycle। তোমাকে সেই redundant edge-টা খুঁজে ফেরত দিতে হবে, যেটা সরালে আবার tree হয়ে যায়। একাধিক উত্তর সম্ভব হলে input-এ শেষে আসা edge-টা দাও।

edges = (1-2) (1-3) (2-3)
        1-2-3-1 একটা cycle; শেষে আসা cycle-edge (2-3)  ->  উত্তর: [2,3]

2. Which basic idea does this inherit from?

মূল ভিত হলো এই tracker-এর cycle pattern (#4 Graph Valid Tree) — undirected graph-এ union যখন দুটো already-connected node-এ চলে, তখন সেই edge cycle বন্ধ করে আর union False ফেরায়। #4-এ আমরা শুধু "cycle আছে কি না" জানতে চেয়েছিলাম; এখানে এক ধাপ এগিয়ে প্রথম যে edge False ফেরায়, সেটাই উত্তর।

3. What is the hidden math or logic?

লুকানো logic: একটা tree-তে যেকোনো একটা extra edge ঠিক একটা cycle তৈরি করে। তুমি edge-গুলো input-order-এ একে একে union করছ; যতক্ষণ tree গড়ে উঠছে প্রতিটা union সফল (True)। ঠিক যেই edge-টা দুটো আগেই-যুক্ত node জোড়ার চেষ্টা করে, সেটাই cycle বন্ধ করে — আর যেহেতু input-order মানছ, এই প্রথম False-edge-ই হলো "শেষে আসা" redundant edge।

4. Which data structure is needed?

একটা DSU (parent + size array), node 1 থেকে n পর্যন্ত (এই problem-এ node 1-indexed)। edge-গুলো union-এর কাঁচামাল; প্রথম যে union False দেয় তার (u, v) ফেরত দিই।

5. Why this data structure fits

প্রশ্নটা বিশুদ্ধ cycle-edge খোঁজা — path বা distance নয়। DSU-র union return মানসিকভাবে একটা cycle-detector: edge merge করে দিলে True, আর আগেই-যুক্ত হলে False। এই False-ই আমাদের চাওয়া edge ধরিয়ে দেয়, কোনো DFS back-edge খোঁজা ছাড়াই — তাই DSU সবচেয়ে পরিষ্কার fit।

6. Real-life analogy

party-র friend circle, তবে এবার তুমি গোয়েন্দা। মানুষ একে একে পরিচিত হচ্ছে আর circle গড়ে উঠছে। হঠাৎ দুজন হাত মেলায় যারা আগে থেকেই এক circle-এ — এই হাত-মেলানোটা নতুন কিছু জোড়ে না, স্রেফ একটা অপ্রয়োজনীয় বন্ধন (redundant)। তুমি ঠিক ওই প্রথম অপ্রয়োজনীয় হাত-মেলানোটাকে চিহ্নিত করো।

7. Visual explanation

edge-গুলো input-order-এ union করো; প্রথম যেটা False ফেরায় সেটাই redundant।

edges: (1-2) (1-3) (2-3)

শুরু:   *1  *2  *3            parent: [_,1,2,3]   (index 0 unused)

union(1,2): roots 1,2 আলাদা -> True
        *1   *3
         |
         2                    parent: [_,1,1,3]

union(1,3): find(1)=1, find(3)=3 আলাদা -> True
        *1
       /  \
      2    3                  parent: [_,1,1,1]

union(2,3): find(2)=1, find(3)=1  ->  সমান!  ->  False
            (2 আর 3 আগেই এক circle, এই edge cycle বন্ধ করছে)
            redundant = [2, 3]

------ longer cycle: edges (1-2)(2-3)(3-4)(1-4)(1-5) ------
union(1,2) T ; union(2,3) T ; union(3,4) T ;
union(1,4): find(1)=1, find(4)=1 -> False  ->  redundant = [1,4]
(পরের (1-5) আর দেখাই হয় না — প্রথম False-ই উত্তর)

8. Example input and output

Input : edges=[[1,2],[1,3],[2,3]]
Output: [2,3]

Input : edges=[[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Input : edges=[[1,2],[2,3],[1,3]]
Output: [1,3]

9. Brute force thinking

সরল চিন্তা: প্রতিটা edge একটা একটা করে সরিয়ে দেখো বাকি n−1 edge দিয়ে graph এখনো connected আর acyclic থাকে কি না (অর্থাৎ tree)। প্রথম যে edge সরালে tree হয় — শেষ থেকে শুরু করলে — সেটাই উত্তর।

1) edge-গুলো শেষ থেকে দেখো
2) প্রতিটা candidate edge বাদ দিয়ে DFS/BFS চালাও
3) বাকিটা যদি tree হয় (connected, acyclic) -> সেই edge-ই redundant

10. Why brute force is slow

প্রতিটা edge বাদ দিয়ে আলাদা করে tree-check মানে O(E) বার DFS — মোট O(E·(V+E)), edge সংখ্যার সাথে quadratic-ঘেঁষা। DSU একবারই, একটা pass-এ, প্রতিটা edge merge করতে করতে প্রথম False-edge-এ থেমে যায় — মোট O(E·α) ≈ O(E)। বাড়তি কোনো graph নতুন করে চষা লাগে না।

11. Key observation

মূল observation: input-order বজায় রেখে union করলে, প্রথম False-edge-ই হলো "শেষে আসা" redundant edge। যেহেতু shape একটা tree + ঠিক একটা extra edge, ঠিক একটাই False ঘটে — তাই প্রথম False-এই উত্তর নিশ্চিত, আর order মানায় tie-break-ও নিজে থেকে ঠিক।

12. Optimized intuition

edge-গুলো input-order-এ union করো; যেই edge False ফেরায়, সাথে সাথে সেটা ফেরত দাও। DSU array node 1..n ধরে নিতে size n+1 রাখো (1-indexed)। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(n)।

13. Thinking tweak

মোচড়: "কোন edge সরালে tree হবে, এক এক করে পরখ করি" — এই পরীক্ষা-নিরীক্ষার চিন্তা ছাড়ো। বদলে ভাবো "edge-গুলো জোড়া লাগাতে লাগাতে প্রথম যেটা দুটো আগেই-যুক্ত জিনিস জোড়ার চেষ্টা করে, সেটাই বাড়তি।" cycle detection-কে cycle-edge খোঁজায় বদলে দাও।

14. Step-by-step dry run

Input edges=[[1,2],[2,3],[3,4],[1,4],[1,5]]:

1. union(1,2) → roots 1,2 আলাদা → True, merge → {1,2}
2. union(2,3) → find(2)=1, find(3)=3 আলাদা → True → {1,2,3}
3. union(3,4) → find(3)=1, find(4)=4 আলাদা → True → {1,2,3,4}
4. union(1,4) → find(1)=1, find(4)=1 → সমান → False → redundant = [1,4], সাথে সাথে return
5. (edge [1,5] আর দেখাই হয় না)

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_connection(edges):
    n = len(edges)                       # edge-সংখ্যা == node-সংখ্যা (tree + 1)
    dsu = DSU(n + 1)                     # node 1..n -> size n+1 (1-indexed)
    for u, v in edges:
        if not dsu.union(u, v):          # প্রথম False -> এই edge cycle বন্ধ করছে
            return [u, v]
    return []                            # statement বলে সবসময় একটা থাকবে


# ---- tests ----
assert find_redundant_connection([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
assert find_redundant_connection([[1, 2], [2, 3], [1, 3]]) == [1, 3]
print("সব test pass!")

16. Line-by-line code explanation

• n = len(edges) — এই graph-এ node-সংখ্যা edge-সংখ্যার সমান (tree-র n−1 edge + 1 বাড়তি = n edge, আর n node)।
• dsu = DSU(n + 1) — node 1-indexed, তাই index n পর্যন্ত পৌঁছাতে array size n+1 (index 0 অব্যবহৃত)।
• for u, v in edges: if not dsu.union(u, v) — edge-গুলো input-order-এ merge; union False মানে u আর v আগেই যুক্ত, অর্থাৎ এই edge cycle বন্ধ করছে।
• return [u, v] — প্রথম False-edge-ই "শেষে আসা" redundant edge; order মানায় tie-break আপনাআপনি ঠিক।
• return [] — কখনো পৌঁছায় না (statement একটা redundant edge-এর নিশ্চয়তা দেয়); defensive।

17. Output walkthrough

প্রথম test-এ 1-2, 1-3 merge সফল; 2-3 দুটো আগেই-যুক্ত node, False → [2,3]। দ্বিতীয়টায় 1-2-3-4 chain গড়ে; 1-4 cycle বন্ধ করে False → [1,4] (পরের 1-5 দেখাই হয় না)। তৃতীয়টায় 1-2, 2-3 merge; 1-3 redundant → [1,3]। শেষে print: সব test pass!।

18. Time complexity

O(E · α(V)) ≈ O(E) — প্রতিটা edge বড়জোর একটা union/দুটো find, প্রতিটা amortized near-constant (inverse Ackermann, বাস্তবে ≤ 4)। প্রথম False-এ থেমে গেলে আরও কম।

19. Space complexity

O(V) — শুধু parent আর size array (size n+1); কোনো adjacency list নেই।

20. Common mistakes

• DSU array size n-এ নেওয়া যখন node 1-indexed — index n ছুঁলেই out-of-range; n+1 লাগে।
• প্রথম False-এ না থেমে loop চালিয়ে যাওয়া আর শেষ False-edge ফেরানো — এখানে ঠিক একটাই cycle, তাই প্রথম False-ই উত্তর; তবে দেরি করলেও ঠিক আসে, শুধু অপচয়।
• "শেষে আসা" tie-break ভুলে input-order উল্টে union করা — তখন ভুল edge ফেরে।

21. Which basic problem this inherits from

ভিত্তি: এই tracker-এর Graph Valid Tree (#4) — সেখানে union-এর False দিয়ে "cycle আছে কি না" জেনেছিলে; এখানে সেই প্রথম False-edge-টাই ফেরত দিচ্ছ। মূল fact "tree + এক extra edge = এক cycle" ../../09-graphs/concept.md-তেও আছে। concept.md-র "এক comparison-এ cycle detection" snippet-ই কার্যত এই problem-এর পুরো solution।

22. Similar harder problems

• Graph Valid Tree (শুধু হ্যাঁ/না, edge ফেরাতে হয় না) — https://leetcode.com/problems/graph-valid-tree/ (এই tracker-এর #4)
• Redundant Connection II (directed graph, double-parent + cycle কেস একসাথে) — https://leetcode.com/problems/redundant-connection-ii/ (#16)
• Number of Operations to Make Network Connected (cycle-edge গুনে spare হিসেবে কাজে লাগানো) — https://leetcode.com/problems/number-of-operations-to-make-network-connected/ (#6)

23. Pattern learned

Cycle detection (edge-locating রূপ): edge-গুলো input-order-এ union করো; প্রথম False-edge-ই cycle-closer, সেটাই redundant। "redundant edge" বা "edge that can be removed" শুনলে এই প্রথম-False-এ-থামা trick সরাসরি খাটে; order বজায় রাখলে tie-break-ও নিজে থেকে মেলে।

24. Final summary

ভবিষ্যতের আমাকে: "কোন edge সরালে আবার tree হবে?" দেখলে edge পরীক্ষা-নিরীক্ষা ছাড়ো — input-order-এ union চালাও, যেই edge দুটো আগেই-যুক্ত node জোড়ার চেষ্টা করে (False), সেটাই উত্তর, সাথে সাথে ফেরত দাও। এটাই cycle-edge খোঁজার সবচেয়ে পরিষ্কার রূপ।

25. JavaScript solution (with test cases)

DSU class (path compression + union by size); edge input-order-এ union, প্রথম false-edge-ই redundant।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);   // প্রথমে সবাই নিজের root
    this.size = new Array(n).fill(1);
  }
  find(x) {                                  // representative + path halving
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(x, y) {                              // merge হলে true, আগে-যুক্ত হলে false
    let rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;             // আগে থেকেই এক group -> cycle
    if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
    this.parent[ry] = rx;
    this.size[rx] += this.size[ry];
    return true;
  }
}
// edges 1-indexed; edge-সংখ্যা == node-সংখ্যা (tree + 1 extra)
function findRedundantConnection(edges) {
  const n = edges.length;
  const dsu = new DSU(n + 1);                // node 1..n -> size n+1
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v];     // প্রথম false -> cycle বন্ধ করছে
  }
  return [];
}
// ---- test cases (example + edge) ----
assert(JSON.stringify(findRedundantConnection([[1, 2], [1, 3], [2, 3]])) === "[2,3]", "triangle");
assert(JSON.stringify(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])) === "[1,4]", "longer-cycle");
assert(JSON.stringify(findRedundantConnection([[1, 2], [2, 3], [1, 3]])) === "[1,3]", "last-edge");
console.log("সব JS test pass!");

JS টীকা: DSU array দুটো বানাতে Array.from({length:n}, (_, i) => i) (parent) আর new Array(n).fill(1) (size) — fill(1) নিরাপদ কারণ 1 primitive, কিন্তু কখনো object/array দিয়ে .fill() কোরো না (সব ঘরে এক reference)। ফেরত edge [u,v] array, তাই === দিয়ে নয়, JSON.stringify দিয়ে তুলনা করো (reference নয়, মান মেলাতে)।

26. TypeScript solution (with test cases)

class DSU {
  private parent: number[];
  private size: number[];
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(x: number, y: number): boolean {
    let rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
    this.parent[ry] = rx;
    this.size[rx] += this.size[ry];
    return true;
  }
}
function findRedundantConnection(edges: number[][]): number[] {
  const n: number = edges.length;
  const dsu = new DSU(n + 1);
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v];
  }
  return [];
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp)) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expectArr(findRedundantConnection([[1, 2], [1, 3], [2, 3]]), [2, 3], "triangle");
expectArr(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]), [1, 4], "longer");
expectArr(findRedundantConnection([[1, 2], [2, 3], [1, 3]]), [1, 3], "last");
console.log("সব TS test pass!");

TS টীকা: private parent/private size দিয়ে DSU-র ভেতরের array বাইরে থেকে দুর্ঘটনাবশত বদলানো আটকানো হয় (encapsulation); find/union-এর signature (number → number, boolean) ফাংশন-চুক্তি locked করে, ভুল type-এর node পাঠালে compile-error।

27. কোথায় কাজে লাগে (real-world use)

• Network redundancy detection: কোন cable/link সরালে network এখনো connected থাকে (অপ্রয়োজনীয় redundant link) — তা চিহ্নিত করা।
• Cycle-causing edge খোঁজা: একটা spanning structure-এ কোন সংযোগ চক্র তৈরি করছে — DSU-র প্রথম false-union।
• Circuit / graph validation: tree হওয়ার কথা এমন structure-এ বাড়তি edge ধরা (যেমন একটা valid hierarchy ভাঙছে কোথায়)।
• Build/dependency sanity: যেখানে acyclic থাকার কথা, সেখানে কোন নির্ভরতা চক্র আনছে তা locate করা।
• Incremental connectivity: edge একে একে যোগ করতে করতে কোনটা "নতুন কিছু জোড়ে না" তা সাথে সাথে জানা।

মূল pattern: edge input-order-এ union করো; প্রথম যেটা দুটো আগেই-যুক্ত node জোড়ার চেষ্টা করে (false), সেটাই redundant।

---

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