Problem link ও উৎস
- **Original source:** Classic connected-components exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Easy-Medium
- **Pattern:** component counting
- **Basic idea inherited from:** [../../09-graphs/](../../09-graphs/README.md)-এর DFS version (ওখানে #6); এখানে আমরা DFS-এর বদলে union করে component গুনি
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা city আর একটা `n × n` matrix `isConnected` দেওয়া; `isConnected[i][j] == 1` মানে i আর j সরাসরি যুক্ত। একটা **province** হলো এমন city-দের দল, যারা সরাসরি বা ঘুরিয়ে (transitively) যুক্ত। তোমাকে province-এর মোট সংখ্যা গুনতে হবে।
```text
isConnected =
1 1 0
1 1 0
0 0 1
city 0 ও 1 যুক্ত (এক province); city 2 একা (আরেক province) -> উত্তর: 2
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
party-র friend circle আবার। শুরুতে n জন, n টা circle। প্রতিবার দুজন অপরিচিত মানুষ মেলে আর তাদের circle মেশে — circle-সংখ্যা একটা কমে। আগেই-পরিচিত দুজন আবার হাত মেলালে কিছুই বদলায় না। শেষে যত circle টিকে থাকে, ততগুলো province।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **connected components গোনা**। [../../09-graphs/](../../09-graphs/README.md)-এ তুমি এটা 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 ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: matrix থেকে adjacency list বানাও, একটা `visited` array রাখো, তারপর প্রতিটা না-দেখা city থেকে DFS/BFS চালাও আর counter বাড়াও।
```text
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-এর সাথে সাথেই হয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
Matrix-এর প্রতিটা `1` (উপরের ত্রিভুজ) union; counter n থেকে শুরু করে successful merge-এ কমাও।
```text
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
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[1,1,0],[1,1,0],[0,0,1]]`, `components = 3`:
1. cell (0,1) = 1 → `union(0,1)` সফল → `components = 2`
2. cell (0,2) = 0 → skip
3. cell (1,2) = 0 → skip
4. আর কোনো 1 নেই → loop শেষ
5. return `components` = **2**
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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-সংখ্যাই উত্তর।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ব্যবহার না করা — দুবার কাজ।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../09-graphs/](../../09-graphs/README.md)-এর "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) —