006 — Number of Operations to Make Network Connected

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic connectivity-cost exercise
• Platform: LeetCode — https://leetcode.com/problems/number-of-operations-to-make-network-connected/
• 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

n টা computer (0 থেকে n−1) আর কতগুলো cable connections দেওয়া; প্রতিটা cable দুটো computer-কে সরাসরি জোড়ে। তুমি একটা cable খুলে অন্য দুই computer-এ লাগাতে পারো। সব computer connect করতে কমপক্ষে কত বার cable সরাতে হবে — সেটা বলো। সম্ভব না হলে −1।

উদাহরণ

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

উদাহরণ

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

চেনা উদাহরণে বোঝা

party-র friend circle, তবে এবার তোমার হাতে সীমিত "introduction" আছে। ঘরে কয়েকটা আলাদা circle। তুমি জানো — c টা circle-কে এক করতে c−1 টা নতুন পরিচয় লাগবে। আর যদি দুজন আগেই-পরিচিত মানুষ আবার পরিচিত হয়, ওই পরিচয়টা "অপচয়" — সেটাকে অন্য দুই অপরিচিতের মাঝে কাজে লাগাও। যথেষ্ট অপচয় থাকলেই সবাইকে এক করা যায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

দুটো ভিত একসাথে: component counting (#2) — কয়টা আলাদা দল আছে; আর cycle counting (concept.md-র cycle guard) — কয়টা cable redundant (যাদের union False ফেরায়)। একটা redundant cable মানে একটা spare যা খুলে অন্যত্র লাগানো যায়। দুটো সংখ্যা মিললেই উত্তর।

ভেতরের যুক্তি

লুকানো 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।

কী দিয়ে তথ্য রাখব

একটা DSU (parent + size array) আর একটা components counter। cable-গুলো union-এ খাইয়ে component গুনি; এর বেশি কিছু লাগে না।

এটি কেন উপযুক্ত

প্রশ্ন দুটো DSU-জিনিস চায়: কয়টা component (merge-গোনা) আর enough spare আছে কি না (cable-count vs n−1)। DSU merge-only দুনিয়ায় এ দুটোই সহজ — union-এর return দিয়ে component কমাও, আর মোট cable গুনে রাখো। Path/distance অপ্রাসঙ্গিক, তাই DSU সবচেয়ে হালকা fit।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: adjacency list বানাও, DFS দিয়ে component গোনো; আলাদা করে cable scan করে redundant (cycle) cable গোনো; তারপর components−1 ≤ spare হলে উত্তর components−1, নাহলে দেখো cable-সংখ্যা যথেষ্ট কি না।

উদাহরণ

1) DFS দিয়ে components গোনো
2) redundant cable (cycle-closing) আলাদা গোনো
3) cable < n-1 হলে -> -1
4) নাহলে -> components - 1

কোথায় বেশি কাজ হচ্ছে

DFS version O(V+E) হলেও এতে adjacency গড়া, recursion, visited bookkeeping, আর spare গোনার জন্য আলাদা logic লাগে। DSU একই pass-এ component-ও গোনে, আর spare গোনার দরকারই ফেলে দেয় — কারণ cable ≥ n−1 হলেই enough spare guaranteed। তাই code ছোট, একটাই scan।

যে বিষয়টি খেয়াল করতে হবে

মূল observation দুটো: (১) c টা component জোড়াতে ঠিক c−1 cable লাগে; (২) cable-সংখ্যা ≥ n−1 হলেই যথেষ্ট spare আছে (spare আলাদা গোনা লাগে না)। তাই উত্তর হয় −1 (cable < n−1), নয়তো components − 1।

আরও কম কাজে সমাধান

প্রথমে 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)।

ভাবনার পরিবর্তন

মোচড়: "spare cable কয়টা, আর component কয়টা — দুটো আলাদা করে গুনে মেলাই" — এই দ্বৈত-গোনার চিন্তা সরল করো। বদলে ভাবো "cable ≥ n−1 হলে spare নিয়ে দুশ্চিন্তাই নেই; উত্তর শুধু components − 1।" একটা inequality পুরো spare-গোনার কাজ মুছে দেয়।

ছবিতে বোঝা

cable union করে component গোনো; উত্তর = components − 1 (যদি cable ≥ n−1)।

উদাহরণ

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-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

প্রথম 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

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

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<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(makeConnected(4, [[0, 1], [0, 2], [1, 2]]), 1, "one-spare");
expect(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]), 2, "two-comp");
expect(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]), -1, "too-few");
expect(makeConnected(1, []), 0, "single");
console.log("সব TS test pass!");

TS টীকা: connections: number[][] typing দিয়ে প্রতিটা cable যে দুই-সংখ্যার জোড়া তা locked; return type number (উত্তর বা -1) ফাংশন-চুক্তি পরিষ্কার করে; private DSU field encapsulation দিয়ে ভেতরের state দুর্ঘটনাবশত বদলানো রোধ করে।

খরচ ও সাধারণ ভুল

সময়

O((n + E) · α(n)) ≈ O(n + E) — DSU init O(n); প্রতিটা cable একটা union, প্রতিটা amortized near-constant (inverse Ackermann, বাস্তবে ≤ 4)।

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

• spare cable আলাদা করে গোনার চেষ্টা করা — অহেতুক; cable ≥ n−1 check-ই enough spare নিশ্চিত করে।
• len(connections) < n−1 early check ভুলে যাওয়া — তখন impossible case-এ ভুল (negative বা ভুল) উত্তর আসতে পারে।
• উত্তরে components ফেরানো components − 1-এর বদলে — c দলকে এক করতে c−1 cable লাগে, c নয়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: এই tracker-এর Number of Provinces (#2) — সেখানে শিখেছ "successful union গুনে component গোনা"; এখানে সেই component-সংখ্যা থেকে −1 করে cable-হিসাব করছ। সাথে concept.md-র cycle-counting (spare = union-এর False)। DFS দিয়েও component গোনা যায়; graph fixed আর একবার দেখলে DFS সমান fast, কিন্তু DSU-তে spare-গোনা প্রায় বিনামূল্যে।

পরের অনুশীলন

• Graph Valid Tree (component=1 আর শূন্য cycle হলে tree) — https://leetcode.com/problems/graph-valid-tree/ (এই tracker-এর #4)
• Redundant Connection (যে cable spare, সেটা চিহ্নিত করা) — https://leetcode.com/problems/redundant-connection/ (#5)
• Accounts Merge (component গোনার আরেক প্রয়োগ) — https://leetcode.com/problems/accounts-merge/ (#9)

কৌশলটি মনে রাখুন

Components + spare edges: components = n বসাও, সফল union-এ −1 করো; cable < n−1 হলে impossible (−1), নাহলে উত্তর components − 1। "everything connect করতে কত move?" জাতীয় প্রশ্নে এই "merge-গোনা + edge-count guard" combo সরাসরি খাটে; spare আলাদা গোনা লাগে না।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "সব connect করতে কত operation?" দেখলে দুটো সংখ্যা ভাবো — কয়টা component, আর cable ≥ n−1 কি না। cable কম হলে −1; নাহলে উত্তর শুধু components − 1। spare cable নিয়ে আলাদা মাথা ঘামানোর দরকার নেই — n−1 থাকলেই enough।

কোথায় কাজে লাগে

• Network connectivity planning: কয়টা আলাদা cluster আছে আর সবাইকে জুড়তে কয়টা নতুন link দরকার — DSU দিয়ে গোনা।
• Infrastructure / cabling cost: বিদ্যমান redundant cable খুলে কোথায় লাগালে পুরো network connected হয়, ন্যূনতম move-এ।
• Cluster merging: distributed system-এ partition-গুলো এক করতে ন্যূনতম কত নতুন সংযোগ দরকার।
• Spanning-structure feasibility: n node connect করতে অন্তত n−1 edge লাগে — পর্যাপ্ত edge আছে কিনা দ্রুত যাচাই।
• Social / entity graph: কয়টা আলাদা community আছে আর সবাইকে এক করতে কয়টা bridge দরকার।

মূল pattern: "সব connect করতে কত operation?" = কয়টা component, আর edge ≥ n−1 কিনা; উত্তর components − 1।

---

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