Problem link ও উৎস
- **Original source:** Classic grid-connectivity exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** grid cells as DSU elements
- **Basic idea inherited from:** [../../09-graphs/](../../09-graphs/README.md)-এর DFS version (ওখানে #4); এখানে grid cell-কে DSU node বানিয়ে component গুনি
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `m × n` grid দেওয়া, প্রতিটা cell `'1'` (land) বা `'0'` (water)। একটা **island** হলো পাশাপাশি (উপর/নিচ/বাঁ/ডান) যুক্ত land-cell-দের দল। তোমাকে island-এর মোট সংখ্যা গুনতে হবে।
```text
grid =
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
উপরের-বাঁয়ের 1-গুলো এক island; মাঝের একা 1 আরেকটা; নিচের-ডানের জোড়া আরেকটা
-> উত্তর: 3
```
### Input ও output {#8-example-input-and-output}
```text
Input :
[["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]]
Output: 1
Input :
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
Output: 3
Edge case (সব জল): [["0","0"],["0","0"]] -> 0
Edge case (একটাই land): [["1"]] -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বিশাল ছকে আঁকা জমি, কিছু ঘর "শুকনো জমি" কিছু "জল"। প্রতিটা শুকনো ঘর শুরুতে নিজের একটা ছোট দ্বীপ। তুমি ডান আর নিচ বরাবর হাঁটো; দুটো শুকনো ঘর পাশাপাশি দেখলে তাদের দ্বীপ এক করে দাও (union)। সব হাঁটা শেষে যত আলাদা দ্বীপ টিকে থাকে, সেটাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো [../../09-graphs/](../../09-graphs/README.md)-এর **Number of Islands DFS (ওখানে #4)** — সেখানে প্রতিটা না-দেখা land থেকে DFS চালিয়ে পুরো island "ডুবিয়ে" এসে গুনেছ। এখানে grid-কে graph হিসেবে দেখি যেখানে **প্রতিটা land-cell একটা DSU node**, আর পাশাপাশি land-cell দুটো union করি; island-সংখ্যা = land component-সংখ্যা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic concept.md-র **component count rule** grid-এ প্রয়োগ: শুরুতে প্রতিটা land-cell আলাদা component ধরে `land` counter গুনি; পাশের দুই land merge হলে component একটা কমে। তাই island-সংখ্যা = (মোট land) − (সফল union)। 2D position-কে 1D index-এ map করার সূত্র: cell `(r, c)` → `r * cols + c` — তাহলেই grid একটা সাধারণ DSU হয়ে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** `rows × cols` element-এর (প্রতিটা cell একটা সম্ভাব্য node), আর একটা `land` counter। শুধু land-cell গুনি, আর প্রতিটা land-cell-এর ডান ও নিচের প্রতিবেশী land হলে union করি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা "কয়টা আলাদা land-দল?" — বিশুদ্ধ component counting, path নয়। DSU merge-only দুনিয়ায় grid cell-গুলো জুড়তে জুড়তে দল কমে — ঠিক যা দরকার। DFS-ও পারে, কিন্তু DSU streaming/online variant-এ (#13 Number of Islands II) সরাসরি বাড়ানো যায়, যা traversal পারে না — তাই grid-এ DSU শেখা মূল্যবান।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা (`09-graphs` version): grid scan করো; প্রতিটা না-দেখা land-cell পেলে count বাড়াও আর DFS/BFS চালিয়ে পুরো island-টা `'0'` করে দাও (বা visited mark করো), যাতে আবার গোনা না হয়।
```text
1) প্রতি cell ঘোরো
2) '1' আর না-দেখা হলে -> count += 1, DFS শুরু
3) DFS চারদিকের যুক্ত '1' সব visited করে দেয়
4) count = island-সংখ্যা
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
DFS version O(m·n)-ই, কার্যত fast — DSU এখানে asymptotically দ্রুত নয়। আসল পার্থক্য **নমনীয়তায়**: DFS প্রতিবার পুরো island নতুন করে চষে, তাই cell **একটা একটা করে যোগ হলে** (streaming, #13) প্রতিবার পুরো traversal লাগে — অপচয়। DSU আগের merge মনে রাখে, তাই incremental update-এ স্বাভাবিক। Static একবারের গোনায় দুটোই সমান।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা cell-কে শুধু ডান আর নিচ প্রতিবেশীর সাথে union করলেই যথেষ্ট।** চারদিক দেখার দরকার নেই — কারণ scan যখন এক cell-এ পৌঁছায়, তার বাঁ আর উপরের প্রতিবেশী আগেই process হয়ে গেছে আর তখন তারা **এই** cell-কে দেখেছিল। তাই অর্ধেক কাজে সব জোড়া একবার করেই ধরা পড়ে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`rows × cols`-size DSU নাও আর `land = 0`। grid scan করো; প্রতিটা `'1'` cell-এ `land += 1`, তারপর তার ডান (`r, c+1`) আর নিচ (`r+1, c`) প্রতিবেশী যদি land হয়, union করো; সফল union-এ `land -= 1`। শেষে `land`-ই island-সংখ্যা। মোট O(m·n·α)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতি island-এ DFS চালিয়ে ডুবিয়ে আসি" — এই traversal চিন্তার পাশে আরেকটা রাখো। ভাবো "প্রতিটা land প্রথমে একটা আলাদা দ্বীপ; পাশের দুই land পেলে দ্বীপ জোড়া লাগাই, counter কমাই।" cell = node, adjacency = union — grid-কে DSU-চোখে দেখাই চাবি (বিশেষত streaming variant-এর জন্য)।
### ছবিতে বোঝা {#7-visual-explanation}
land গুনতে গুনতে শুধু ডান ও নিচ প্রতিবেশীর সাথে union করো; প্রতি সফল merge-এ counter কমাও।
```text
grid: 1 1 0
1 0 0
0 0 1 index = r*3 + c
land cells: (0,0)=0 (0,1)=1 (1,0)=3 (2,2)=8
শুরু: land = 4 (প্রতিটা land আলাদা)
cell (0,0)=land: ডান (0,1) land -> union(0,1) সফল -> land = 3
নিচ (1,0) land -> union(0,3) সফল -> land = 2
cell (0,1)=land: ডান (0,2) water -> skip
নিচ (1,1) water -> skip
cell (1,0)=land: ডান (1,1) water; নিচ (2,0) water -> skip
cell (2,2)=land: ডান নেই; নিচ নেই -> skip
ফল: components -> {(0,0),(0,1),(1,0)} আর {(2,2)} = 2 island
------ সব 0 হলে: কোনো land নেই -> land = 0 ------
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[["1","1","0"],["0","1","0"],["0","0","1"]]`, cols=3 (cell গোনার পরপরই তার নিচ+ডান প্রতিবেশীর সাথে union হয়):
1. শুরু: `land = 0`
2. (0,0)='1' → land=1; নিচ(1,0)='0' skip; ডান(0,1)='1' → `union(0,1)` সফল → land=0
3. (0,1)='1' → land=1; নিচ(1,1)='1' → `union(1,4)` সফল → land=0; ডান(0,2)='0' skip
4. (1,1)='1' → land=1; নিচ(2,1)='0' skip; ডান(1,2)='0' skip
5. (2,2)='1' → land=1; কোনো প্রতিবেশী land নেই → final **land = 2**
6. দুই island: {(0,0),(0,1),(1,1)} আর {(2,2)} → return **2**
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n # প্রতিটা group-এ একজন
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 # rx এখন বড় root
self.parent[ry] = rx # ছোটটা বড়টার নিচে ঝোলে
self.size[rx] += self.size[ry]
return True
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
dsu = DSU(rows * cols) # প্রতিটা cell একটা সম্ভাব্য node
land = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
land += 1 # নতুন land -> আপাতত আলাদা island
idx = r * cols + c # 2D -> 1D index
if r + 1 < rows and grid[r + 1][c] == "1": # নিচ প্রতিবেশী
if dsu.union(idx, (r + 1) * cols + c):
land -= 1 # merge হলো -> island একটা কমলো
if c + 1 < cols and grid[r][c + 1] == "1": # ডান প্রতিবেশী
if dsu.union(idx, r * cols + c + 1):
land -= 1
return land
# ---- tests ----
assert num_islands([
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"],
]) == 1
assert num_islands([
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"],
]) == 3
assert num_islands([["0", "0"], ["0", "0"]]) == 0 # সব জল
assert num_islands([["1"]]) == 1 # একটাই land
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dsu = DSU(rows * cols)` — প্রতিটা cell একটা সম্ভাব্য node, তাই DSU-র size cell-সংখ্যা।
- `land += 1` — নতুন land-cell পেলে প্রথমে আলাদা island ধরে নিই; merge হলে পরে কমবে।
- `idx = r * cols + c` — 2D position-কে এক-মাত্রিক index-এ map; grid এতে সাধারণ DSU হয়ে যায়।
- নিচ ও ডান প্রতিবেশী check — bound-এ থাকলে আর land হলে union; **শুধু এই দুই দিক** যথেষ্ট, কারণ বাঁ/উপর আগেই process হয়ে এই cell-কে দেখেছে।
- `if dsu.union(...): land -= 1` — সফল merge (দুই আলাদা component জোড়া) হলেই island একটা কমে; একই component হলে `False`, কিছু বদলায় না।
- `return land` — টিকে থাকা land-component-সংখ্যাই island-সংখ্যা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ বাঁ-উপরের সব 1 ডান/নিচ union-এ এক component হয়ে যায় — 1 island। দ্বিতীয়টায় তিন আলাদা গুচ্ছ কখনো পাশাপাশি হয় না — 3 island। সব-জল case-এ একটাও land নেই, land থাকে 0। single-land case-এ একটা land, কোনো প্রতিবেশী নেই — 1। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m · n · α(m·n))** ≈ **O(m · n)** — প্রতিটা cell একবার দেখা, প্রতিটায় বড়জোর দুটো union, প্রতিটা amortized near-constant। DFS version-ও O(m·n) — এখানে DSU asymptotically সমান।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m · n)** — `parent` + `size` array cell-সংখ্যার সমান। DFS-এর recursion stack-ও worst case O(m·n), তাই space-ও তুলনীয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- চার দিক (উপর/নিচ/বাঁ/ডান) union করা — কাজ করে কিন্তু দ্বিগুণ; scan-order-এ শুধু নিচ আর ডান যথেষ্ট।
- `land += 1` করার পরে merge-এ `land -= 1` করতে ভুলে যাওয়া — তখন প্রতিটা land আলাদা গোনা থেকে যায়, উত্তর বেশি আসে।
- 2D→1D index ভুল (`r * rows + c` লেখা `r * cols + c`-এর বদলে) — non-square grid-এ index ধাক্কা খায়।
- bound check বাদ দেওয়া — শেষ row/column-এ index out-of-range।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../09-graphs/](../../09-graphs/README.md)-এর Number of Islands DFS (ওখানে #4) — সেখানে island ডুবিয়ে গুনেছ, এখানে cell union করে component গুনছ। **DSU-vs-traversal:** static একবারের গোনায় দুটোই O(m·n), DFS তর্কসাপেক্ষে simpler; কিন্তু cell একটা একটা করে **যোগ হলে** (streaming) DFS প্রতিবার পুরো traversal চায়, DSU আগের merge মনে রাখে — সেখানেই DSU জেতে (#13 Number of Islands II দেখো)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Islands II (cell streaming যোগ — যেটা traversal ভালো পারে না) —