Problem link ও উৎস
- **Original source:** Classic two-coloring / bipartiteness exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** BFS/DFS two-coloring (bipartite check)
- **Basic idea inherited from:** BFS levels ([../bfs.md](../bfs.md)); DFS traversal ([../dfs.md](../dfs.md)); queue ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা undirected graph দেওয়া আছে adjacency list হিসেবে — `graph[u]` হলো `u`-এর প্রতিবেশীদের list। বলো: এই graph কি **bipartite**? মানে, সব node-কে কি দুটো দলে (ধরো লাল ও নীল) এমনভাবে ভাগ করা যায়, যাতে প্রতিটা edge সবসময় এক লাল আর এক নীল node-কে জোড়ে — কখনো এক দলের ভেতরে edge না থাকে? পারলে `True`, না পারলে `False`। (graph disconnected হতে পারে।)
```text
graph: 0-1, 1-2, 2-3, 3-0 (একটা 4-চক্র)
দল ভাগ: {0,2} লাল, {1,3} নীল -> প্রতিটা edge দুই রঙের মাঝে -> True
```
### Input ও output {#8-example-input-and-output}
```text
Input : graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True (জোড়-দৈর্ঘ্যের চক্র)
Input : graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False (1-2 edge একই দলে পড়তে বাধ্য -> বিজোড় চক্র)
Edge case (কোনো edge নেই): graph = [[],[],[]] -> True (সব আলাদা, তুচ্ছভাবে bipartite)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা টুর্নামেন্ট ভাবো যেখানে কিছু খেলোয়াড়ের মধ্যে "প্রতিদ্বন্দ্বী" সম্পর্ক আছে (edge মানে এরা একে অন্যের বিপক্ষে খেলবে)। তুমি সবাইকে দুটো দলে ভাগ করতে চাও যাতে প্রতিটা প্রতিদ্বন্দ্বিতা সবসময় দুই দলের মাঝে হয়, এক দলের ভেতরে কেউ কারো প্রতিদ্বন্দ্বী না থাকে। একজনকে দল A দাও, তার সব প্রতিদ্বন্দ্বীকে দল B, তাদের প্রতিদ্বন্দ্বীদের আবার দল A — ছড়াতে থাকো। যদি কখনো এমন কাউকে পাও যাকে ইতিমধ্যে যে দল দিয়েছ, তোমার এখন তার উল্টো দল দরকার — দ্বন্দ্ব! তখন এমন ভাগ অসম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **BFS layer-by-layer expansion** ([../bfs.md](../bfs.md)) আর **DFS traversal** ([../dfs.md](../dfs.md))। BFS-এ even layer-গুলো এক রঙ, odd layer-গুলো অন্য রঙ দিলেই two-coloring তৈরি হয়ে যায় — কারণ প্রতিটা edge পাশাপাশি দুই layer-কে জোড়ে। DFS-এ একই কাজ: একটা node রং করো, প্রতিটা প্রতিবেশীকে উল্টো রঙ দাও। তাই এটা চেনা traversal-এর উপর শুধু একটা "color" বসানো — নতুন কোনো algorithm নয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **একটা graph bipartite তখনই, যখন তাতে কোনো odd-length cycle নেই।** two-coloring-এ প্রতিবেশীকে সবসময় উল্টো রঙ দিতে চাও; কোনো cycle-এর দৈর্ঘ্য জোড় হলে রং পরিষ্কারভাবে আবার মেলে, বিজোড় হলে কোথাও দুই একই-রঙ node পাশাপাশি পড়ে যায় — তখন bipartite অসম্ভব। তাই traversal চালিয়ে প্রতিটা node-কে প্রতিবেশীর উল্টো রঙ দাও; যদি কখনো এমন প্রতিবেশী পাও যাকে আগেই **একই** রঙ দেওয়া হয়েছে — conflict, return `False`। কোনো conflict ছাড়া সব রং করা গেলে `True`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **adjacency list** (input-ই) — প্রতিটা node-এর প্রতিবেশী।
- **color array/map** — প্রতিটা node-এর রং: `-1` (অরঙা), `0`, বা `1`।
- **`collections.deque` (BFS)** বা **recursion stack (DFS)** — graph traverse করতে।
- **disconnected handling** — প্রতিটা node থেকে একবার শুরু করার জন্য বাইরের loop।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Color array fit করে কারণ দুটো দল মানে দুটো মান (`0`/`1`), আর `1 - color` দিয়ে তাৎক্ষণিক উল্টো রঙ পাওয়া যায়; `-1` দিয়ে "এখনো রঙ হয়নি" বোঝে, তাই আলাদা visited লাগে না (রঙ থাকা = visited)। BFS/DFS দুটোই fit করে কারণ bipartite-চেক structural — distance নয়, রঙের সঙ্গতি; তাই যেকোনো traversal চলে। বাইরের loop fit করে কারণ graph disconnected হতে পারে, প্রতিটা component আলাদা করে রং করা দরকার।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব সম্ভাব্য দুই-দলে ভাগ চেষ্টা করে দেখা — প্রতিটা node-কে দল A বা B দেওয়ার সব `2^n` সমাবেশ ঘুরে, প্রতিটা assignment-এ যাচাই করা সব edge দুই দলের মাঝে পড়ছে কিনা।
```text
1) প্রতিটা node-কে A/B দেওয়ার প্রতিটা সম্ভাব্য combination নাও
2) সেই combination-এ সব edge চেক করো — দুই প্রান্ত আলাদা দলে?
3) কোনো combination সব edge পাস করালে True; কোনোটাই না করালে False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`2^n` assignment ঘুরে দেখা **exponential** — সামান্য বড় graph-এও অসম্ভব। অথচ রঙ আসলে স্বাধীন নয়: একটা node-এর রঙ ঠিক হলে তার প্রতিবেশীদের রঙ বাধ্যতামূলকভাবে উল্টো — কোনো পছন্দই নেই। তাই একটা traversal-এ রঙ "ছড়িয়ে" দিলেই হয়, আর শুধু দেখো কোথাও দ্বন্দ্ব হয় কিনা — O(V + E)। সব combination চেষ্টা করা পুরোপুরি অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা node-এর রঙ স্থির হলে তার সব প্রতিবেশীর রঙ বাধ্যতামূলক (উল্টো)।** তাই কোনো পছন্দ বা search নেই — শুধু একটা node থেকে রঙ ছড়িয়ে দাও, আর প্রথম যেখানে দুই একই-রঙ প্রতিবেশী পাশাপাশি পড়ে, সেখানেই bipartiteness ভেঙে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`color` array `-1`-এ শুরু। প্রতিটা node থেকে (disconnected-এর জন্য) — যদি অরঙা থাকে — তাকে রঙ `0` দিয়ে BFS/DFS শুরু করো। traversal-এ প্রতিটা প্রতিবেশীর জন্য: অরঙা হলে `1 - color[cur]` দাও আর এগোও; ইতিমধ্যে রঙ থাকলে সেটা `1 - color[cur]` কিনা যাচাই করো — না হলে (একই রঙ) return `False`। সব component দ্বন্দ্ব ছাড়া রঙ হলে `True`। O(V + E)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব রকম দুই-দলে ভাগ চেষ্টা করব" না ভেবে ভাবো "একটা রঙ ঠিক করলে বাকি সব রঙ নিজে থেকেই ঠিক হয়ে যায় — শুধু traverse করে দ্বন্দ্ব খুঁজি।" search থেকে নেমে এসো একটা rng-ছড়ানো traversal-এ, যেখানে প্রতিবেশী সবসময় উল্টো রঙ।
### ছবিতে বোঝা {#7-visual-explanation}
`graph = [[1,3],[0,2],[1,3],[0,2]]` (4-চক্র 0-1-2-3-0) দিয়ে BFS coloring:
```text
node: 0 1 2 3
edges: 0-1, 1-2, 2-3, 3-0
BFS from 0, color 0 = red(R):
0 -> R
প্রতিবেশী 1,3 -> B (উল্টো)
1-এর প্রতিবেশী 2 -> R ; 3-এর প্রতিবেশী 2 -> R (মিলে যায়, conflict নেই)
R --- B
| | সব edge R<->B -> bipartite
B --- R -> True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`graph = [[1,2,3],[0,2],[0,1,3],[0,2]]` (বিজোড় চক্র 0-1-2):
1. `color = [-1,-1,-1,-1]`। node 0 অরঙা → `color[0] = 0`, BFS শুরু, queue `[0]`।
2. pop `0` → প্রতিবেশী `1` (অরঙা) → `color[1]=1`, enqueue; `2` (অরঙা) → `color[2]=1`, enqueue; `3` (অরঙা) → `color[3]=1`, enqueue।
3. pop `1` → প্রতিবেশী `0` (color 0 = `1 - 1` ✓); `2` (color 1, কিন্তু দরকার `1 - color[1] = 0`) → দ্বন্দ্ব! `color[2]=1` অথচ 1-এর প্রতিবেশী হিসেবে 0 হওয়া উচিত।
4. return `False`। (0-1-2 একটা 3-দৈর্ঘ্যের বিজোড় চক্র, তাই bipartite নয়।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def is_bipartite_bfs(graph):
n = len(graph)
color = [-1] * n # -1 = অরঙা; রঙ থাকা মানেই visited
for start in range(n): # disconnected: প্রতিটা component
if color[start] != -1:
continue
color[start] = 0
q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1: # অরঙা প্রতিবেশী -> উল্টো রঙ
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]: # একই রঙ পাশাপাশি -> দ্বন্দ্ব
return False
return True
def is_bipartite_dfs(graph):
# একই idea, recursion দিয়ে (../dfs.md)
n = len(graph)
color = [-1] * n
def dfs(u, c):
color[u] = c
for v in graph[u]:
if color[v] == -1:
if not dfs(v, 1 - c): # প্রতিবেশীকে উল্টো রঙ
return False
elif color[v] == c: # একই রঙ -> দ্বন্দ্ব
return False
return True
for start in range(n):
if color[start] == -1 and not dfs(start, 0):
return False
return True
# ---- tests ----
g1 = [[1, 3], [0, 2], [1, 3], [0, 2]] # জোড় চক্র -> True
g2 = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]] # বিজোড় চক্র -> False
g3 = [[], [], []] # edge নেই -> True
g4 = [[1], [0], [3], [2]] # দুটো আলাদা edge -> True
assert is_bipartite_bfs(g1) is True
assert is_bipartite_bfs(g2) is False
assert is_bipartite_bfs(g3) is True
assert is_bipartite_bfs(g4) is True
assert is_bipartite_dfs(g1) is True
assert is_bipartite_dfs(g2) is False
assert is_bipartite_dfs(g3) is True
assert is_bipartite_dfs(g4) is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `color = [-1] * n` — `-1` দ্বৈত: অরঙা ও unvisited; রঙ বসানোই visited-marking।
- `for start in range(n): if color[start] != -1: continue` — disconnected graph-এর প্রতিটা component আলাদা করে রঙ শুরু।
- `color[v] = 1 - color[u]` — প্রতিবেশীকে সবসময় উল্টো রঙ; `1 - 0 = 1`, `1 - 1 = 0`।
- `elif color[v] == color[u]: return False` — already-রঙা প্রতিবেশী একই রঙের হলে two-coloring ভেঙে গেছে।
- BFS-এ enqueue ঠিক রঙ বসানোর পাশে — mark-on-push।
- DFS version-এ `dfs(v, 1 - c)` — recursion-এ প্রতিবেশীকে উল্টো রঙে নামা; `False` উপরে propagate হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`is_bipartite_bfs(g1)`: 0→red, 1 ও 3→blue, 2→red; সব edge দুই রঙের মাঝে → `True`। `g2`-তে 0→0, 1→1, 2→1, কিন্তু edge 1-2 দুই একই-রঙ node জোড়ে → `False`। `g3` edge নেই → `True`। `g4` দুই আলাদা edge, প্রতিটা দুই রঙে → `True`। DFS version-ও একই ফল। সব assert pass, শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Python-এর BFS two-coloring হুবহু JS-এ; `color` array `-1`/`0`/`1`, প্রতিবেশীকে `1 - color[u]`।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// adjacency list input; -1 = অরঙা, রঙ থাকা মানেই visited
function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1);
for (let start = 0; start < n; start++) { // disconnected: প্রতিটা component
if (color[start] !== -1) continue;
color[start] = 0;
const queue = [start];
let head = 0; // array-as-queue, index দিয়ে front
while (head < queue.length) {
const u = queue[head++];
for (const v of graph[u]) {
if (color[v] === -1) { // অরঙা -> উল্টো রঙ
color[v] = 1 - color[u];
queue.push(v);
} else if (color[v] === color[u]) { // একই রঙ পাশাপাশি -> দ্বন্দ্ব
return false;
}
}
}
}
return true;
}
// ---- test cases (example + edge) ----
assert(isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) === true, "even-cycle");
assert(isBipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) === false, "odd-cycle");
assert(isBipartite([[], [], []]) === true, "no-edge"); // edge
assert(isBipartite([[1], [0], [3], [2]]) === true, "two-edges");
console.log("সব JS test pass!");
```
> **JS টীকা:** BFS-এর queue হিসেবে `array.shift()` ব্যবহার এড়াও — সেটা O(n), পুরো BFS-কে O(V·E) বানিয়ে দেয়; বদলে একটা `head` index বাড়িয়ে front পড়ো (উপরে যেভাবে)। আর `new Array(n).fill(-1)` নিরাপদ কারণ `-1` একটা primitive — কিন্তু object/array দিয়ে `.fill()` করলে সব ঘরে **একই reference** বসে (পরের section-গুলোতে এই ফাঁদ আসবে)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function isBipartite(graph: number[][]): boolean {
const n: number = graph.length;
const color: number[] = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue;
color[start] = 0;
const queue: number[] = [start];
let head = 0;
while (head < queue.length) {
const u: number = queue[head++];
for (const v of graph[u]) {
if (color[v] === -1) {
color[v] = 1 - color[u];
queue.push(v);
} else if (color[v] === color[u]) {
return false;
}
}
}
}
return true;
}
function expect