Problem link ও উৎস
- **Original source:** Classic cycle-edge exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** cycle detection
- **Basic idea inherited from:** `10`-এর cycle pattern (#4); এখানে শুধু cycle ধরাই নয়, **কোন edge** cycle বন্ধ করল সেটাও ফেরত দিতে হয়
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা graph শুরু হয়েছিল tree হিসেবে (n টা node, n−1 edge), তারপর একটা **বাড়তি** edge যোগ করা হয়েছে — ফলে মোট n edge আর ঠিক একটা cycle। তোমাকে সেই **redundant edge**-টা খুঁজে ফেরত দিতে হবে, যেটা সরালে আবার tree হয়ে যায়। একাধিক উত্তর সম্ভব হলে input-এ **শেষে আসা** edge-টা দাও।
```text
edges = (1-2) (1-3) (2-3)
1-2-3-1 একটা cycle; শেষে আসা cycle-edge (2-3) -> উত্তর: [2,3]
```
### Input ও output {#8-example-input-and-output}
```text
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]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
party-র friend circle, তবে এবার তুমি গোয়েন্দা। মানুষ একে একে পরিচিত হচ্ছে আর circle গড়ে উঠছে। হঠাৎ দুজন হাত মেলায় যারা **আগে থেকেই** এক circle-এ — এই হাত-মেলানোটা নতুন কিছু জোড়ে না, স্রেফ একটা অপ্রয়োজনীয় বন্ধন (redundant)। তুমি ঠিক ওই প্রথম অপ্রয়োজনীয় হাত-মেলানোটাকে চিহ্নিত করো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা edge একটা একটা করে সরিয়ে দেখো বাকি n−1 edge দিয়ে graph এখনো connected আর acyclic থাকে কি না (অর্থাৎ tree)। প্রথম যে edge সরালে tree হয় — শেষ থেকে শুরু করলে — সেটাই উত্তর।
```text
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 খোঁজায় বদলে দাও।
### ছবিতে বোঝা {#7-visual-explanation}
edge-গুলো input-order-এ union করো; প্রথম যেটা `False` ফেরায় সেটাই redundant।
```text
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-ই উত্তর)
```
### ছোট input-এ ধাপে ধাপে {#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]` আর দেখাই হয় না)
## কোড ও ব্যাখ্যা {#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_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।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
DSU class (path compression + union by size); edge input-order-এ union, প্রথম `false`-edge-ই redundant।
```javascript
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 নয়, মান মেলাতে)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ফেরে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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](../../09-graphs/concept.md)-তেও আছে। concept.md-র "এক comparison-এ cycle detection" snippet-ই কার্যত এই problem-এর পুরো solution।
### পরের অনুশীলন {#22-similar-harder-problems}
- Graph Valid Tree (শুধু হ্যাঁ/না, edge ফেরাতে হয় না) —