Problem link ও উৎস
- **Original source:** Classic connectivity-cost exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** components + spare edges
- **Basic idea inherited from:** `10`-এর component counting (#2) আর cycle counting; spare cable = redundant edge, আর components−1 = লাগবে এমন cable
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা computer (0 থেকে n−1) আর কতগুলো cable `connections` দেওয়া; প্রতিটা cable দুটো computer-কে সরাসরি জোড়ে। তুমি একটা cable **খুলে** অন্য দুই computer-এ লাগাতে পারো। সব computer connect করতে **কমপক্ষে কত বার** cable সরাতে হবে — সেটা বলো। সম্ভব না হলে `−1`।
```text
n = 4, connections = (0-1) (0-2) (1-2)
{0,1,2} এক group + {3} একা = 2 component; 0-1-2-এ একটা cable redundant
সেটা খুলে 3-এ লাগাও -> উত্তর: 1
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4, connections=[[0,1],[0,2],[1,2]]
Output: 1
Input : n=6, connections=[[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2
Input : n=6, connections=[[0,1],[0,2],[0,3],[1,2]]
Output: -1 (4 cable < n-1 = 5)
Edge case (single node): n=1, connections=[] -> 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
party-র friend circle, তবে এবার তোমার হাতে সীমিত "introduction" আছে। ঘরে কয়েকটা আলাদা circle। তুমি জানো — c টা circle-কে এক করতে c−1 টা নতুন পরিচয় লাগবে। আর যদি দুজন আগেই-পরিচিত মানুষ আবার পরিচিত হয়, ওই পরিচয়টা "অপচয়" — সেটাকে অন্য দুই অপরিচিতের মাঝে কাজে লাগাও। যথেষ্ট অপচয় থাকলেই সবাইকে এক করা যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত একসাথে: **component counting (#2)** — কয়টা আলাদা দল আছে; আর **cycle counting** (concept.md-র cycle guard) — কয়টা cable redundant (যাদের `union` `False` ফেরায়)। একটা redundant cable মানে একটা **spare** যা খুলে অন্যত্র লাগানো যায়। দুটো সংখ্যা মিললেই উত্তর।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই অংশে:
- **কত cable লাগবে:** `c` টা component-কে এক করতে ঠিক **c − 1** টা নতুন connection লাগে (প্রতিটা cable একটা merge, প্রতি merge component একটা কমায়)।
- **কত spare আছে:** যেকোনো cable যেটা দুটো **আগেই-যুক্ত** computer জোড়ে, সেটা redundant — খুলে ফেলা যায় ক্ষতি ছাড়াই।
মূল গাণিতিক shortcut: spare আলাদা করে গোনারই দরকার নেই। যদি মোট cable-সংখ্যা **≥ n − 1** হয়, তাহলে সব component জোড়ার মতো যথেষ্ট spare সবসময় থাকে — উত্তর শুধু **components − 1**। আর cable < n − 1 হলে কখনোই সম্ভব না — `−1`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`parent` + `size` array) আর একটা `components` counter। cable-গুলো `union`-এ খাইয়ে component গুনি; এর বেশি কিছু লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্ন দুটো DSU-জিনিস চায়: কয়টা component (merge-গোনা) আর enough spare আছে কি না (cable-count vs n−1)। DSU merge-only দুনিয়ায় এ দুটোই সহজ — `union`-এর return দিয়ে component কমাও, আর মোট cable গুনে রাখো। Path/distance অপ্রাসঙ্গিক, তাই DSU সবচেয়ে হালকা fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: adjacency list বানাও, DFS দিয়ে component গোনো; আলাদা করে cable scan করে redundant (cycle) cable গোনো; তারপর components−1 ≤ spare হলে উত্তর components−1, নাহলে দেখো cable-সংখ্যা যথেষ্ট কি না।
```text
1) DFS দিয়ে components গোনো
2) redundant cable (cycle-closing) আলাদা গোনো
3) cable < n-1 হলে -> -1
4) নাহলে -> components - 1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
DFS version O(V+E) হলেও এতে adjacency গড়া, recursion, visited bookkeeping, আর spare গোনার জন্য আলাদা logic লাগে। DSU একই pass-এ component-ও গোনে, আর spare গোনার দরকারই ফেলে দেয় — কারণ cable ≥ n−1 হলেই enough spare guaranteed। তাই code ছোট, একটাই scan।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation দুটো: **(১)** c টা component জোড়াতে ঠিক **c−1** cable লাগে; **(২)** cable-সংখ্যা **≥ n−1** হলেই যথেষ্ট spare আছে (spare আলাদা গোনা লাগে না)। তাই উত্তর হয় `−1` (cable < n−1), নয়তো `components − 1`।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে `len(connections) < n−1` হলে সরাসরি `−1`। নাহলে `components = n` বসিয়ে সব cable `union` করো, সফল merge-এ `components -= 1`। শেষে উত্তর `components − 1`। spare গোনার দরকারই নেই — n−1 cable থাকা মানেই enough spare। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(n + E)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "spare cable কয়টা, আর component কয়টা — দুটো আলাদা করে গুনে মেলাই" — এই দ্বৈত-গোনার চিন্তা সরল করো। বদলে ভাবো "cable ≥ n−1 হলে spare নিয়ে দুশ্চিন্তাই নেই; উত্তর শুধু components − 1।" একটা inequality পুরো spare-গোনার কাজ মুছে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
cable union করে component গোনো; উত্তর = components − 1 (যদি cable ≥ n−1)।
```text
n = 4, cables: (0-1) (0-2) (1-2) components = 4
শুরু: *0 *1 *2 *3 components = 4
union(0,1) সফল: components = 3
*0 *2 *3
|
1
union(0,2) সফল: components = 2
*0 *3
/ \
1 2
union(1,2): find(1)=0, find(2)=0 -> False (spare cable!) components = 2 (অপরিবর্তিত)
*0 *3
/ \
1 2
components = 2 -> জোড়া লাগাতে লাগবে 2 - 1 = 1 cable
spare আছে (ওই 1-2) -> উত্তর: 1
------ cable < n-1 case: n=6, মাত্র 4 cable ------
4 < 6-1 = 5 -> কখনো সবাইকে জোড়া যাবে না -> -1
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `n=6, connections=[[0,1],[0,2],[0,3],[1,2],[1,3]]`:
1. cable-সংখ্যা = 5 ≥ n−1 = 5 → সম্ভব, এগোও; `components = 6`
2. `union(0,1)` সফল → `components = 5`
3. `union(0,2)` সফল → `components = 4`
4. `union(0,3)` সফল → `components = 3`
5. `union(1,2)` → find=0,0 → `False` (spare) → `components = 3`
6. `union(1,3)` → find=0,0 → `False` (spare) → `components = 3`
7. উত্তর = `components − 1` = 3 − 1 = **2**
## কোড ও ব্যাখ্যা {#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 -> spare cable
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 make_connected(n, connections):
if len(connections) < n - 1: # n-1 cable না থাকলে কখনো সম্ভব না
return -1
dsu = DSU(n)
components = n
for u, v in connections:
if dsu.union(u, v): # সফল merge -> এক component কমলো
components -= 1
return components - 1 # c component জোড়াতে c-1 cable লাগে
# ---- tests ----
assert make_connected(4, [[0, 1], [0, 2], [1, 2]]) == 1
assert make_connected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]) == 2
assert make_connected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]) == -1 # cable < n-1
assert make_connected(1, []) == 0 # একটাই node
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if len(connections) < n - 1: return -1` — n node-কে এক করতে অন্তত n−1 cable লাগেই; কম থাকলে কোনো বিন্যাসেই সম্ভব না।
- `components = n` — শুরুতে প্রত্যেক computer আলাদা component।
- `for u, v in connections: if dsu.union(u, v)` — প্রতিটা cable merge করার চেষ্টা; `True` মানে দুই আলাদা group জোড়া লাগল।
- `components -= 1` — সফল merge-এ component একটা কমে; `False` (spare cable) হলে কিছু বদলায় না।
- `return components - 1` — টিকে থাকা `components` দলকে এক করতে ঠিক `components − 1` cable লাগে; n−1 cable থাকায় enough spare guaranteed।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ {0,1,2} আর {3} = 2 component, 1-2 spare; উত্তর 2−1 = 1। দ্বিতীয়টায় 3 component (দুটো cable spare), উত্তর 3−1 = 2। তৃতীয়টায় 4 cable < n−1 = 5, তাই −1। single-node case-এ ইতিমধ্যেই 1 component, উত্তর 0। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
DSU class; cable < n−1 হলে `-1`, নাহলে `components = n` থেকে সফল union-এ কমিয়ে উত্তর `components − 1`।
```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) {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]]; // path halving
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; // spare cable
if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
this.parent[ry] = rx;
this.size[rx] += this.size[ry];
return true;
}
}
// n computer (0..n-1), connections[]; সব connect করতে min cable-move, অসম্ভব হলে -1
function makeConnected(n, connections) {
if (connections.length < n - 1) return -1; // n-1 cable না থাকলে কখনো সম্ভব না
const dsu = new DSU(n);
let components = n;
for (const [u, v] of connections) {
if (dsu.union(u, v)) components--; // সফল merge -> এক component কমলো
}
return components - 1; // c component জোড়াতে c-1 cable
}
// ---- test cases (example + edge) ----
assert(makeConnected(4, [[0, 1], [0, 2], [1, 2]]) === 1, "one-spare");
assert(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]) === 2, "two-comp");
assert(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]) === -1, "too-few-cable"); // edge
assert(makeConnected(1, []) === 0, "single-node");
console.log("সব JS test pass!");
```
> **JS টীকা:** `connections.length` দিয়ে cable-সংখ্যা পাও — Python-এর `len()`-এর সমতুল্য। DSU array দুটো `Array.from(..., (_, i) => i)` (parent) আর `new Array(n).fill(1)` (size); object দিয়ে কখনো `.fill()` কোরো না (shared reference)। `union`-এর boolean return দিয়ে component-গণনা চালানো — `false` (spare cable) হলে `components` অপরিবর্তিত।
### 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 makeConnected(n: number, connections: number[][]): number {
if (connections.length < n - 1) return -1;
const dsu = new DSU(n);
let components: number = n;
for (const [u, v] of connections) {
if (dsu.union(u, v)) components--;
}
return components - 1;
}
function expect