Problem link ও উৎস
- **Original source:** Classic connected-components exercise (adjacency matrix form)
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** connected components on an adjacency matrix
- **Basic idea inherited from:** components/traversal (এই tracker-এর #2 ও #4); পরে আবার করো [../../10-disjoint-set-union/](../../10-disjoint-set-union/README.md) দিয়ে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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`।)
```text
isConnected: শহর 0--1 জোড়া, শহর 2 একা
1 1 0
1 1 0 -> 2 টা province: {0,1} আর {2}
0 0 1
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা ক্লাসে বন্ধুত্বের তালিকা ভাবো — কে কার সরাসরি বন্ধু, একটা বড় টেবিলে টিক চিহ্ন দিয়ে লেখা (সারি ও কলামে সবার নাম)। "কতগুলো আলাদা বন্ধু-দল" জানতে চাও — যেখানে এক দলের যে কেউ অন্যজনের কাছে বন্ধুর-বন্ধু ধরে পৌঁছায়। একজনকে বেছে নাও, তার বন্ধু, বন্ধুর বন্ধু — সবাইকে দাগিয়ে এক দল সম্পূর্ণ করো। তারপর তালিকায় অদাগানো নতুন কাউকে খোঁজো, পেলে আরেকটা দল। যতবার নতুন করে শুরু করলে, ততগুলো দল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: কোন শহর কোন province-এ তা label করতে বারবার পুরো matrix স্ক্যান করা — যেমন প্রতিবার একটা নতুন জোড়া `(i, j)` দেখে তাদের label মেলানোর চেষ্টা, আর label বদলালে আবার পুরো তালিকা ঘোরা, যতক্ষণ না কিছুই বদলায়।
```text
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/](../../10-disjoint-set-union/README.md)-এ ফিরে এসো।)
### যে বিষয়টি খেয়াল করতে হবে {#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-এর চেহারায় বিভ্রান্ত না হয়ে নিচের গ্রাফটা দেখো।
### ছবিতে বোঝা {#7-visual-explanation}
`isConnected = [[1,1,0],[1,1,0],[0,0,1]]` দিয়ে দেখি:
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`isConnected = [[1,0,0],[0,1,0],[0,0,1]]` (কেউ কারো সাথে জোড়া নয়):
1. `count = 0`, `seen = {}`। scan শুরু।
2. শহর `0` তাজা → `count = 1`। DFS: `0`-এর সারি `[1,0,0]` → প্রতিবেশী শুধু নিজে (`j=0`, কিন্তু seen)। province `{0}` শেষ।
3. শহর `1` তাজা → `count = 2`। DFS: সারি `[0,1,0]` → প্রতিবেশী শুধু নিজে। province `{1}` শেষ।
4. শহর `2` তাজা → `count = 3`। DFS: সারি `[0,0,1]` → শুধু নিজে। province `{2}` শেষ।
5. scan শেষ। return `count = 3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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-তে পুনরাবৃত্তি ঠেকায়।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` দেখা — তাহলে অর্ধেক সংযোগ মিস; পুরো সারি পড়ো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: components/reachability (#2, #4) আর traversal ([../dfs.md](../dfs.md), [../bfs.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) —