002 — Number of Provinces¶

Source¶

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 গুনি

1. Problem in simple words¶

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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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

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

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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 আরও স্বাভাবিক।

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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

16. Line-by-line code explanation¶

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-সংখ্যাই উত্তর।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Number of Operations to Make Network Connected (component + spare edge) — https://leetcode.com/problems/number-of-operations-to-make-network-connected/ (এই tracker-এর #6)
Accounts Merge (key share করে component) — https://leetcode.com/problems/accounts-merge/ (#9)
Number of Islands (grid cell = DSU node) — https://leetcode.com/problems/number-of-islands/ (#10)

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "কয়টা 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।