006 — Number of Operations to Make Network Connected

Source

• 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

1. Problem in simple words

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

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।

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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

9. Brute force thinking

সরল চিন্তা: 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

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-গোনার কাজ মুছে দেয়।

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

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

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• 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 নয়।

21. Which basic problem this inherits from

ভিত্তি: এই 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-গোনা প্রায় বিনামূল্যে।

22. Similar harder problems

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

23. Pattern learned

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

24. Final summary

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

25. JavaScript solution (with test cases)

DSU class; cable < n−1 হলে -1, নাহলে components = n থেকে সফল union-এ কমিয়ে উত্তর components − 1।

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 অপরিবর্তিত।

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 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 দুর্ঘটনাবশত বদলানো রোধ করে।

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

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