006 — Number of Provinces¶

Source¶

Original source: Classic connected-components exercise (adjacency matrix form)
Platform: LeetCode — https://leetcode.com/problems/number-of-provinces/
Topic: graphs
Difficulty: Medium
Pattern: connected components on an adjacency matrix
Basic idea inherited from: components/traversal (এই tracker-এর #2 ও #4); পরে আবার করো ../../10-disjoint-set-union/ দিয়ে

1. Problem in simple words¶

n টা শহর আছে। তোমাকে একটা n x n matrix isConnected দেওয়া হয়েছে, যেখানে isConnected[i][j] = 1 মানে শহর i আর শহর j সরাসরি জোড়া, আর 0 মানে জোড়া নয়। একটা province হলো এমন একগুচ্ছ শহর, যাদের প্রত্যেকেই সরাসরি বা অন্য শহরের মাধ্যমে একে অন্যের সাথে যুক্ত। কতগুলো আলাদা province আছে, সেটা গোনো। (matrix symmetric, আর diagonal-এ isConnected[i][i] = 1।)

isConnected:        শহর 0--1 জোড়া, শহর 2 একা
  1 1 0
  1 1 0             -> 2 টা province: {0,1} আর {2}
  0 0 1

2. Which basic idea does this inherit from?¶

মূল ভিত হলো connected components (#2-এর reachability আর #4-এর island গোনা)। province মানেই connected component — গ্রাফের ভাষায় island-ই। তফাত শুধু input-এর চেহারায়: এখানে edge গুলো একটা adjacency matrix-এ দেওয়া, grid বা edge list-এ নয়। তাই একই components-গোনা reflex, শুধু "প্রতিবেশী কারা" প্রশ্নের উত্তর matrix-এর সারি পড়ে পাওয়া যায়।

3. What is the hidden math or logic?¶

লুকানো logic: province = connected component, আর component গোনা = কতবার নতুন traversal launch করতে হলো। প্রতিটা শহর একবার দেখো; এখনো-না-ছোঁয়া শহর পেলে সেটা একটা নতুন province-এর শুরু — counter বাড়াও, তারপর সেখান থেকে DFS/BFS চালিয়ে ওই province-এর সব শহর (সরাসরি ও পরোক্ষ-যুক্ত) visited mark করো। শহর i-এর প্রতিবেশী হলো সেই সব j, যেখানে isConnected[i][j] == 1। মোট launch সংখ্যাই province সংখ্যা।

4. Which data structure is needed?¶

adjacency matrix নিজেই — input-ই graph; শহর i-এর প্রতিবেশী খুঁজতে তার পুরো সারি স্ক্যান করো।
visited set / array — কোন শহর ইতিমধ্যে কোনো province-এ পড়েছে।
Recursion stack (DFS) বা collections.deque (BFS) — এক province-এর সব শহর explore করতে।

5. Why this data structure fits¶

Matrix-কে সরাসরি graph ধরা fit করে কারণ "i আর j জোড়া কিনা" সরাসরি isConnected[i][j]-এ — O(1)-এ। তবে প্রতিটা শহরের প্রতিবেশী জানতে পুরো সারি (n ঘর) পড়তে হয়, তাই traversal O(n^2)। visited array fit করে কারণ একই province দুবার না গোনা আর cycle এড়ানোর জন্য প্রতিটা শহর একবার process হওয়া দরকার। DFS/BFS দুটোই সমান — components-এ distance লাগে না।

6. Real-life analogy¶

একটা ক্লাসে বন্ধুত্বের তালিকা ভাবো — কে কার সরাসরি বন্ধু, একটা বড় টেবিলে টিক চিহ্ন দিয়ে লেখা (সারি ও কলামে সবার নাম)। "কতগুলো আলাদা বন্ধু-দল" জানতে চাও — যেখানে এক দলের যে কেউ অন্যজনের কাছে বন্ধুর-বন্ধু ধরে পৌঁছায়। একজনকে বেছে নাও, তার বন্ধু, বন্ধুর বন্ধু — সবাইকে দাগিয়ে এক দল সম্পূর্ণ করো। তারপর তালিকায় অদাগানো নতুন কাউকে খোঁজো, পেলে আরেকটা দল। যতবার নতুন করে শুরু করলে, ততগুলো দল।

7. Visual explanation¶

isConnected = [[1,1,0],[1,1,0],[0,0,1]] দিয়ে দেখি:

matrix (সারি i-এর 1-গুলোই প্রতিবেশী):
        0  1  2
   0 [  1  1  0 ]   -> 0-এর প্রতিবেশী: 1
   1 [  1  1  0 ]   -> 1-এর প্রতিবেশী: 0
   2 [  0  0  1 ]   -> 2-এর প্রতিবেশী: (নিজে ছাড়া কেউ না)

DFS from 0: visit 0 -> neighbor 1 -> 1-এর neighbor 0 (seen)। province {0,1} শেষ।
2 এখনো unvisited -> নতুন province {2}।

মোট launch = 2  ->  উত্তর 2

8. Example input and output¶

Input : isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input : isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Edge case (সবাই জোড়া): isConnected = [[1,1],[1,1]] -> 1

9. Brute force thinking¶

প্রথম সরল চিন্তা: কোন শহর কোন province-এ তা label করতে বারবার পুরো matrix স্ক্যান করা — যেমন প্রতিবার একটা নতুন জোড়া (i, j) দেখে তাদের label মেলানোর চেষ্টা, আর label বদলালে আবার পুরো তালিকা ঘোরা, যতক্ষণ না কিছুই বদলায়।

1) প্রতিটা শহরকে আলাদা label দাও
2) প্রতিটা (i,j) জোড়া isConnected[i][j]==1 হলে label এক করার চেষ্টা করো
3) কিছু বদলালে আবার পুরো pass; স্থির হলে আলাদা label-সংখ্যা গোনো

10. Why brute force is slow¶

বারবার pass চালিয়ে label মেলানো effectively একটা দুর্বল union-find — সঠিক হলেও বহু pass-এ খরচ matrix size-এর গুণিতকে ফুলে যায়, আর হাতে track করা ভুলপ্রবণ। অথচ একবার traversal করলে প্রতিটা শহর একবার ছোঁয়া হয়, আর matrix বলে প্রতিটা শহরের প্রতিবেশী খুঁজতে এক সারি (n ঘর) পড়া — মোট O(n^2), যা matrix নিজেই পড়ার সমান। (DSU দিয়ে আরেকটা পরিষ্কার solution — পরে ../../10-disjoint-set-union/-এ ফিরে এসো।)

11. Key observation¶

মূল observation: এখনো-না-ছোঁয়া প্রতিটা শহর ঠিক একটা নতুন province-এর জন্ম দেয়। কারণ সেই শহর থেকে traversal পৌঁছানো-যায় এমন সব শহর একবারেই দখল করে। তাই শহর 0 থেকে n-1 ঘুরতে ঘুরতে যতবার একটা তাজা (unvisited) শহরে হোঁচট খেলে, ততবার counter বাড়ানোই যথেষ্ট।

12. Optimized intuition¶

0 থেকে n-1 শহর scan করো। visited হলে এড়িয়ে যাও। তাজা হলে: counter += 1, তারপর সেই শহর থেকে DFS/BFS — যেখানে প্রতিবেশী = isConnected[node]-এর 1-ওয়ালা index — চালিয়ে গোটা province-টা visited mark করো। scan শেষে counter-ই province সংখ্যা। প্রতিটা শহর traversal-এ একবার, প্রতিবার সারি পড়তে O(n) — মোট O(n^2)।

13. Thinking tweak¶

মোচড়: "input grid নয়, matrix — তাহলে এটা নতুন কোনো problem" না ভেবে চিনে নাও "matrix শুধু edge দেওয়ার আরেকটা ফরম্যাট; প্রতিবেশী = সারির 1-গুলো; বাকিটা হুবহু island/component গোনা।" input-এর চেহারায় বিভ্রান্ত না হয়ে নিচের গ্রাফটা দেখো।

14. Step-by-step dry run¶

isConnected = [[1,0,0],[0,1,0],[0,0,1]] (কেউ কারো সাথে জোড়া নয়):

count = 0, seen = {}। scan শুরু।
শহর 0 তাজা → count = 1। DFS: 0-এর সারি [1,0,0] → প্রতিবেশী শুধু নিজে (j=0, কিন্তু seen)। province {0} শেষ।
শহর 1 তাজা → count = 2। DFS: সারি [0,1,0] → প্রতিবেশী শুধু নিজে। province {1} শেষ।
শহর 2 তাজা → count = 3। DFS: সারি [0,0,1] → শুধু নিজে। province {2} শেষ।
scan শেষ। return count = 3।

15. Python solution¶

from collections import deque


def find_provinces_dfs(is_connected):
    n = len(is_connected)
    seen = [False] * n

    def dfs(city):
        seen[city] = True
        for nb in range(n):
            # প্রতিবেশী = সারির 1-গুলো; নিজেকে (nb == city) এমনিতেই seen ধরা
            if is_connected[city][nb] == 1 and not seen[nb]:
                dfs(nb)

    count = 0
    for city in range(n):
        if not seen[city]:            # তাজা শহর -> নতুন province
            count += 1
            dfs(city)                 # গোটা province দখল করো
    return count


def find_provinces_bfs(is_connected):
    # একই idea, queue দিয়ে (../../04-stack-and-queue/)
    n = len(is_connected)
    seen = [False] * n
    count = 0
    for start in range(n):
        if not seen[start]:
            count += 1
            seen[start] = True        # push করার সময় mark করো
            q = deque([start])
            while q:
                city = q.popleft()
                for nb in range(n):
                    if is_connected[city][nb] == 1 and not seen[nb]:
                        seen[nb] = True
                        q.append(nb)
    return count


# ---- tests ----
m1 = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
m2 = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
m3 = [[1, 1], [1, 1]]
m4 = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]   # {0,3} আর {1,2}

assert find_provinces_dfs(m1) == 2
assert find_provinces_dfs(m2) == 3
assert find_provinces_dfs(m3) == 1
assert find_provinces_dfs(m4) == 2
assert find_provinces_bfs(m1) == 2
assert find_provinces_bfs(m2) == 3
assert find_provinces_bfs(m3) == 1
assert find_provinces_bfs(m4) == 2
print("সব test pass!")

16. Line-by-line code explanation¶

n = len(is_connected) — শহরের সংখ্যা (matrix square)।
seen = [False] * n — প্রতিটা শহর কোনো province-এ পড়েছে কিনা।
dfs(city) — city mark করে, তার সারির প্রতিটা 1-ওয়ালা তাজা nb-তে recurse।
is_connected[city][nb] == 1 and not seen[nb] — প্রতিবেশী আর এখনো-না-দেখা হলেই যাও; nb == city ঘরটা diagonal 1 হলেও আগেই seen, তাই নিরাপদ।
বাইরের loop — প্রতিটা শহর scan; তাজা পেলে count += 1 তারপর dfs।
BFS version-এ seen[nb] = True ঠিক q.append-এর পাশে — push-এর সময় mark, queue-তে পুনরাবৃত্তি ঠেকায়।

17. Output walkthrough¶

find_provinces_dfs(m1): শহর 0 তাজা → count 1, DFS দখল করে {0,1}; শহর 1 আগেই seen; শহর 2 তাজা → count 2। m2-তে কেউ জোড়া নয় → 3। m3 সবাই জোড়া → 1। m4-তে {0,3} আর {1,2} → 2। BFS version-ও একই ফল। সব assert pass, শেষে print: সব test pass!।

18. Time complexity¶

O(n^2) — প্রতিটা শহর traversal-এ একবার, আর প্রতিবার তার পুরো সারি (n ঘর) পড়া হয়। এটা পুরো matrix একবার পড়ারই সমান, যা এই input ফরম্যাটে অনিবার্য।

19. Space complexity¶

O(n) — seen array O(n), আর recursion stack/queue worst case O(n) (এক চেইনে সব শহর যুক্ত থাকলে)। matrix নিজে input, তাই গোনা হয় না।

20. Common mistakes¶

matrix-কে edge list ভেবে ভুল parse করা — এখানে প্রতিবেশী = সারির 1-ওয়ালা index, edge pair নয়।
diagonal isConnected[i][i] = 1-কে আলাদা edge ভেবে গোলমাল করা — নিজেকে seen ধরলে এমনিতেই নিরীহ।
visited না রাখা — symmetric matrix-এ i↔j দুই দিকেই 1, তাই visited ছাড়া infinite loop।
প্রতিবেশী খুঁজতে শুধু j > i দেখা — তাহলে অর্ধেক সংযোগ মিস; পুরো সারি পড়ো।

21. Which basic problem this inherits from¶

ভিত্তি: components/reachability (#2, #4) আর traversal (../dfs.md, ../bfs.md)। এটা island গোনারই (#4) আরেক চেহারা — শুধু input grid নয়, adjacency matrix। মূল শিক্ষা: input-এর ফরম্যাট বদলালেও গ্রাফটা একই; "প্রতিবেশী কীভাবে পাব" বদলায়, components-গোনার reflex বদলায় না। পরের ধাপ: একই components কিন্তু competitive-programming scale-এ (#7)।

22. Similar harder problems¶

Building Roads (components, CP scale, edges minus one) — https://cses.fi/problemset/task/1666 (এই tracker-এর #7)
Number of Islands (grid input-এ component) — https://leetcode.com/problems/number-of-islands/ (#4)
Graph Valid Tree (component + cycle) — https://leetcode.com/problems/graph-valid-tree/

23. Pattern learned¶

Components from any input format: province/island/group গোনা মানেই connected components গোনা — input grid, edge list, না adjacency matrix, তাতে কিছু আসে যায় না। শুধু "প্রতিবেশী কীভাবে পাব" অংশটা input অনুযায়ী বদলে scan-and-flood reflex চালাও। matrix হলে খরচ O(n^2)।

24. Final summary¶

ভবিষ্যতের আমাকে: "province = connected component; matrix মানে প্রতিবেশী = সারির 1-গুলো; বাকিটা island গোনার মতোই — তাজা শহর পেলেই গোটা province দখল করো আর কতবার শুরু করলে গোনো।" input ফরম্যাটে বিভ্রান্ত হয়ো না; পরে এই problem-এ DSU দিয়ে দ্বিতীয় solution লিখে দুই পথের তুলনা করো।

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