006 — Number of Provinces¶

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

Problem link ও উৎস

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/ দিয়ে

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

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

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

Input ও 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

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

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

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

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

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

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

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

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

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

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

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 লাগে না।

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

প্রথম সরল উপায়¶

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

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে¶

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

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

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

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

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

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

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

ছবিতে বোঝা¶

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

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

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।

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

Python¶

Python

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

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

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-তে পুনরাবৃত্তি ঠেকায়।

Output মিলিয়ে দেখা¶

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

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

সময়¶

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

অতিরিক্ত জায়গা¶

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

যে ভুলগুলো এড়াতে হবে¶

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 দেখা — তাহলে অর্ধেক সংযোগ মিস; পুরো সারি পড়ো।

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

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

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

পরের অনুশীলন¶

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/

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

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

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

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