কনটেন্টে যান

002 — Number of Provinces

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

Problem link ও উৎস

  • Original source: Classic connected-components exercise
  • Platform: LeetCode — https://leetcode.com/problems/number-of-provinces/
  • Topic: disjoint set union
  • Difficulty: Easy-Medium
  • Pattern: component counting
  • Basic idea inherited from: ../../09-graphs/-এর DFS version (ওখানে #6); এখানে আমরা DFS-এর বদলে union করে component গুনি

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

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

n টা city আর একটা n × n matrix isConnected দেওয়া; isConnected[i][j] == 1 মানে i আর j সরাসরি যুক্ত। একটা province হলো এমন city-দের দল, যারা সরাসরি বা ঘুরিয়ে (transitively) যুক্ত। তোমাকে province-এর মোট সংখ্যা গুনতে হবে।

উদাহরণ
isConnected =
  1 1 0
  1 1 0
  0 0 1

city 0 ও 1 যুক্ত (এক province); city 2 একা (আরেক province)  ->  উত্তর: 2

Input ও output

উদাহরণ
Input : [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input : [[1,0,0],[0,1,0],[0,0,1]]
Output: 3      (কেউ যুক্ত নয়)

Input : [[1,1,1],[1,1,1],[1,1,1]]
Output: 1      (সবাই এক province)

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

party-র friend circle আবার। শুরুতে n জন, n টা circle। প্রতিবার দুজন অপরিচিত মানুষ মেলে আর তাদের circle মেশে — circle-সংখ্যা একটা কমে। আগেই-পরিচিত দুজন আবার হাত মেলালে কিছুই বদলায় না। শেষে যত circle টিকে থাকে, ততগুলো province।

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

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

মূল ভিত হলো connected components গোনা। ../../09-graphs/-এ তুমি এটা DFS দিয়ে করেছ: প্রতিটা না-দেখা node থেকে DFS চালিয়ে এক component মুছে এসেছ, আর গুনেছ কতবার নতুন DFS শুরু করতে হলো। DSU সেই গোনাটা করে successful union গুনে।

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

লুকানো logic concept.md-র component count rule: শুরুতে group-সংখ্যা = n; প্রতিটা successful union (দুটো সত্যিকারের আলাদা root জোড়া) ঠিক 1 করে group কমায়। তাই উত্তর = n − (successful union-এর সংখ্যা)। কোনো আলাদা গোনাগুনি লাগে না — invariant-টাই হিসাব রাখে।

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

একটা DSU (parent + size array)। Matrix-টা শুধু পড়ার জন্য; আমরা এর 1-গুলো দেখে union চালাই আর একটা components counter কমাই।

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

প্রশ্নটা বিশুদ্ধ "কয়টা দল?" — path বা distance নয়। DSU merge-only দুনিয়ায় ঠিক এই কাজটাই করে: সম্পর্ক জুড়তে জুড়তে দল কমে। Counter একবার বসিয়ে union-এর return দেখে কমালেই answer তৈরি — DFS-এর visited bookkeeping ছাড়াই।

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

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

সরল চিন্তা: matrix থেকে adjacency list বানাও, একটা visited array রাখো, তারপর প্রতিটা না-দেখা city থেকে DFS/BFS চালাও আর counter বাড়াও।

উদাহরণ
1) প্রতি i: যদি visited না হয় -> count += 1, DFS(i)
2) DFS পুরো component-টা visited করে দেয়
3) count = province-সংখ্যা

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

DFS version ঠিকঠাক — O(n²) (matrix scan)। কিন্তু এতে recursion stack, visited array, আর adjacency গড়া লাগে। DSU একই O(n²) matrix scan-এ চলে, তবে কোনো recursion বা adjacency ছাড়াই — শুধু counter আর দুটো array। বড় sparse input বা streaming relation-এ DSU আরও স্বাভাবিক।

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

মূল observation: component গোনা = merge গোনা। তোমাকে শেষে আলাদা করে distinct root গুনতেও হয় না; প্রতিটা সফল union-এ counter একটা কমাও — শেষে counter-ই উত্তর।

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

components = n বসাও। Matrix-এর উপরের ত্রিভুজ ঘুরে যেখানে 1, সেখানে union; return True হলে components -= 1। Loop শেষে components-ই province-সংখ্যা। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(n²)।

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

মোচড়: "কতগুলো আলাদা দল আছে, পরে গুনব" — এই দেরিতে-গোনার চিন্তা ছাড়ো। বদলে ভাবো "প্রতিবার দুটো দল মিশলে মোট দল একটা কমে।" গোনাটা union-এর সাথে সাথেই হয়ে যায়।

ছবিতে বোঝা

Matrix-এর প্রতিটা 1 (উপরের ত্রিভুজ) union; counter n থেকে শুরু করে successful merge-এ কমাও।

উদাহরণ
isConnected (n=3):  1 1 0 / 1 1 0 / 0 0 1     components = 3

শুরু:   *0   *1   *2          parent: [0,1,2]   components = 3

cell (0,1)=1 -> union(0,1) সফল:
        *0   *2               parent: [0,0,2]   components = 2
         |
         1

cell (0,2)=0 -> skip
cell (1,2)=0 -> skip

বাকি কিছু merge হলো না  ->  components = 2

------ যদি সব 1 হতো (n=3): ------
union(0,1) সফল -> 2 ;  union(0,2) সফল -> 1 ;  union(1,2) ব্যর্থ (এক group)
                                              components = 1

ছোট input-এ ধাপে ধাপে

Input [[1,1,0],[1,1,0],[0,0,1]], components = 3:

  1. cell (0,1) = 1 → union(0,1) সফল → components = 2
  2. cell (0,2) = 0 → skip
  3. cell (1,2) = 0 → skip
  4. আর কোনো 1 নেই → loop শেষ
  5. return components = 2

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

Python

Python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n

    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
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True


def find_circle_num(is_connected):
    n = len(is_connected)
    dsu = DSU(n)
    components = n
    for i in range(n):
        for j in range(i + 1, n):        # উপরের ত্রিভুজই যথেষ্ট (symmetric)
            if is_connected[i][j] == 1 and dsu.union(i, j):
                components -= 1          # সফল merge -> এক province কমলো
    return components


# ---- tests ----
assert find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]]) == 2
assert find_circle_num([[1, 0, 0], [0, 1, 0], [0, 0, 1]]) == 3
assert find_circle_num([[1, 1, 1], [1, 1, 1], [1, 1, 1]]) == 1
assert find_circle_num([[1]]) == 1                  # একটাই city
print("সব test pass!")

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

  • components = n — শুরুতে প্রত্যেক city আলাদা province।
  • for j in range(i + 1, n) — matrix symmetric আর diagonal নিজের সাথে নিজে, তাই শুধু উপরের ত্রিভুজ দেখলেই হয় (অর্ধেক কাজ)।
  • is_connected[i][j] == 1 and dsu.union(i, j) — যুক্ত হলে union; short-circuit-এ union তখনই চলে যখন cell 1।
  • components -= 1 — union True ফেরালে (সত্যি merge) তবেই province একটা কমে।
  • return components — টিকে থাকা group-সংখ্যাই উত্তর।

Output মিলিয়ে দেখা

প্রথম test-এ একটাই merge (0–1), তাই 3 থেকে 2। দ্বিতীয়টায় কোনো off-diagonal 1 নেই, কোনো merge নেই — 3 থাকে। তৃতীয়টায় দুটো merge (0–1, 0–2; 1–2 ততক্ষণে এক group, ব্যর্থ) — 3 থেকে 1। single-city case-ও 1। শেষে print: সব test pass!।

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

সময়

O(n² · α(n)) ≈ O(n²) — পুরো matrix একবার scan; প্রতিটা union/find amortized near-constant। Matrix scan-ই dominating খরচ।

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

O(n) — parent + size array। Matrix নিজে input, তার জন্য বাড়তি জায়গা ধরছি না।

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

  • পুরো matrix (j in range(n)) scan করা — কাজ করে, কিন্তু দ্বিগুণ; symmetric বলে উপরের ত্রিভুজই যথেষ্ট।
  • diagonal (isConnected[i][i] = 1) ভুল করে union করা — self-loop, কোনো ক্ষতি নেই তবে অর্থহীন।
  • শেষে আলাদা করে distinct root গুনতে গিয়ে union-এর return ব্যবহার না করা — দুবার কাজ।

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

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

ভিত্তি: ../../09-graphs/-এর "count connected components" DFS (ওখানে #6)। DFS-এ তুমি না-দেখা node থেকে কতবার যাত্রা শুরু হলো গুনেছিলে; এখানে কতবার merge হলো গুনছ — দুটোই একই উত্তরে পৌঁছায়। Graph fixed আর একবারই দেখা হলে DFS সমান fast; DSU তখন এগিয়ে যখন relation স্রোতের মতো আসে।

পরের অনুশীলন

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

Component counting: components = n বসাও, প্রতিটা সফল union-এ একটা কমাও — শেষে counter-ই উত্তর। "কয়টা দল?" জাতীয় যেকোনো প্রশ্নে এই merge-গোনা trick সরাসরি খাটে।

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

ভবিষ্যতের আমাকে: "কয়টা connected group?" দেখলে DFS-এর visited-গোনার বদলে DSU-র merge-গোনা মনে করো — counter n থেকে শুরু, প্রতি সফল union-এ −1। এটা component counting-এর সবচেয়ে পরিষ্কার মন্ত্র।

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