Problem link ও উৎস
- **Original source:** Classic bipartite two-coloring exercise (competitive-programming scale)
- **Platform:** CSES Problem Set —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** bipartite coloring (CP scale)
- **Basic idea inherited from:** bipartite check ([011-is-graph-bipartite.md](011-is-graph-bipartite.md), এই tracker-এর #11); BFS levels ([../bfs.md](../bfs.md)); DFS traversal ([../dfs.md](../dfs.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমার কাছে `n` জন pupil আর `m` টা "এরা দুজন বন্ধু" সম্পর্ক (edge) আছে। সবাইকে ঠিক **দুটো team**-এ ভাগ করতে হবে এমনভাবে, যাতে কোনো বন্ধু-জোড়া একই team-এ না পড়ে — প্রতিটা friendship যেন দুই team-এর মাঝে কাটা পড়ে। সম্ভব হলে প্রতিটা pupil-এর team (`1` বা `2`) ছাপাও; অসম্ভব হলে `IMPOSSIBLE`। এটা হুবহু #11-এর bipartite check, শুধু input বড় আর উত্তরে আসল রঙ-assignment চাই।
```text
pupils 1..5, friendships: 1-2, 1-3, 4-5
team ভাগ: {1,4} -> team 1, {2,3,5} -> team 2
প্রতিটা friendship দুই team-এর মাঝে -> সম্ভব
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=5, edges = [(1,2),(1,3),(4,5)]
Output: [1,2,2,1,2] (pupil 1..5-এর team; কোনো friendship একই team-এ নয়)
Input : n=3, edges = [(1,2),(2,3),(3,1)]
Output: IMPOSSIBLE (1-2-3 একটা বিজোড় চক্র -> দুই team-এ ভাগ অসম্ভব)
Edge case (কোনো friendship নেই): n=3, edges = [] -> [1,1,1] (সবাই team 1-এ দিলেই চলে)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বিতর্ক ক্লাব ভাবো যেখানে কিছু সদস্যের মধ্যে "এরা সবসময় বিপক্ষে দাঁড়ায়" সম্পর্ক আছে (edge)। তুমি সবাইকে দুটো দলে ভাগ করতে চাও যাতে প্রতিটা বিরোধী-জোড়া আলাদা দলে পড়ে, এক দলের ভেতরে কেউ কারো বিপক্ষ না থাকে। একজনকে দল A দাও, তার সব বিপক্ষকে দল B, তাদের বিপক্ষদের আবার দল A — ছড়াতে থাকো। যদি কখনো এমন কাউকে পাও যাকে আগেই দল দিয়েছ অথচ এখন তার উল্টো দল দরকার — দ্বন্দ্ব, এমন ভাগ অসম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো #11-এর **two-coloring** আর তার তলায় থাকা BFS/DFS traversal ([../bfs.md](../bfs.md), [../dfs.md](../dfs.md))। একজন pupil-কে team 1 দাও, তার প্রতিটা বন্ধুকে team 2, তাদের বন্ধুদের আবার team 1 — রঙটা graph জুড়ে ছড়িয়ে দাও। নতুন কিছু নয়: চেনা traversal-এর উপর একটা "team color" বইয়ে নেওয়া, শুধু এবার scale CP-মাপের (`n, m` 10^5 অবধি), তাই recursion-এর বদলে BFS (deque) নিরাপদ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একই সত্য: **graph bipartite তখনই, যখন তাতে কোনো বিজোড়-দৈর্ঘ্যের cycle নেই।** প্রতিটা edge দুই team-এর মাঝে চাই মানে প্রতিবেশীকে সবসময় উল্টো team দিতে চাই; cycle-এর দৈর্ঘ্য জোড় হলে রঙ পরিষ্কারভাবে আবার মেলে, বিজোড় হলে কোথাও দুই একই-team pupil পাশাপাশি পড়ে — তখন ভাগ অসম্ভব। তাই traverse করো, প্রতিবেশীকে উল্টো team দাও; কোনো already-assigned বন্ধু একই team-এ পড়লে conflict → `IMPOSSIBLE`। conflict ছাড়া সব রঙ করা গেলে assignment-টাই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **adjacency list** — `n` বড় বলে matrix নয়, `adj[u]` = বন্ধুদের list।
- **team/color array** — প্রতিটা pupil-এর team: `0` (এখনো না), `1`, বা `2`।
- **`collections.deque`** — BFS traversal; CP-scale-এ recursion overflow এড়াতে।
- **disconnected handling** — friendship graph একাধিক টুকরো হতে পারে, প্রতিটা থেকে আলাদা শুরু লাগবে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
adjacency list fit করে কারণ CP-তে `n, m` বড়, আর O(V + E) traversal-এর জন্য প্রতিটা node-এর প্রতিবেশী দ্রুত দরকার — matrix হলে O(V^2) memory ফেটে যেত। team array fit করে কারণ দুটো দল মানে দুটো মান, আর `3 - team` দিয়ে তাৎক্ষণিক উল্টো team (`3 - 1 = 2`, `3 - 2 = 1`); `0` মানে "এখনো না", তাই আলাদা visited লাগে না। BFS (deque) fit করে কারণ bipartite-চেক structural — distance নয়, রঙের সঙ্গতি; আর deque CP depth-এও নিরাপদ, recursion limit ভাঙে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা pupil-কে team 1 বা 2 দেওয়ার সব `2^n` সমাবেশ ঘুরে দেখা, প্রতিটা assignment-এ যাচাই করা কোনো friendship একই team-এ পড়ছে কিনা।
```text
1) প্রতিটা pupil-কে team 1/2 দেওয়ার প্রতিটা সম্ভাব্য combination নাও
2) সেই combination-এ সব friendship চেক করো — দুই প্রান্ত আলাদা team-এ?
3) কোনো combination সব friendship পাস করালে সেটাই উত্তর; কোনোটাই না করালে IMPOSSIBLE
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`2^n` assignment ঘুরে দেখা **exponential** — `n` 10^5 হলে চিন্তারও বাইরে। অথচ team আসলে স্বাধীন নয়: একজন pupil-এর team ঠিক হলে তার সব বন্ধুর team বাধ্যতামূলকভাবে উল্টো — কোনো পছন্দই নেই। তাই একটা traversal-এ team "ছড়িয়ে" দিলেই হয়, আর শুধু দেখো কোথাও দ্বন্দ্ব হয় কিনা — O(V + E)। সব combination চেষ্টা করা পুরো অপচয়, আর CP time limit-এ তো অসম্ভব।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একজন pupil-এর team স্থির হলে তার সব বন্ধুর team বাধ্যতামূলক (উল্টো)।** তাই কোনো পছন্দ বা search নেই — যেকোনো একজন থেকে team ছড়িয়ে দাও, আর প্রথম যেখানে দুই একই-team বন্ধু পাশাপাশি পড়ে, সেখানেই ভাগ ভেঙে যায় (`IMPOSSIBLE`)। বাকিটা শুধু assignment ছাপানো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`team` array `0`-তে শুরু। প্রতিটা pupil থেকে (disconnected-এর জন্য) — যদি team না থাকে — তাকে team `1` দিয়ে BFS শুরু করো। traversal-এ প্রতিটা বন্ধুর জন্য: team না থাকলে `3 - team[cur]` দাও আর enqueue করো; team থাকলে সেটা `3 - team[cur]` কিনা যাচাই করো — না হলে (একই team) `IMPOSSIBLE`। সব component দ্বন্দ্ব ছাড়া রঙ হলে পুরো assignment-টাই উত্তর। O(V + E)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব রকম দুই-team ভাগ চেষ্টা করব" না ভেবে ভাবো "একজনের team ঠিক করলে বাকি সব team নিজে থেকেই ঠিক হয়ে যায় — শুধু traverse করে দ্বন্দ্ব খুঁজি, আর রঙটাই উত্তর।" search থেকে নেমে এসো একটা রঙ-ছড়ানো BFS-এ, যেখানে বন্ধু সবসময় উল্টো team। CP-তে এক ধাপ যোগ: recursion নয়, deque — depth বড় হলেও নিরাপদ।
### ছবিতে বোঝা {#7-visual-explanation}
`n = 5`, friendships `1-2, 1-3, 4-5` দিয়ে BFS coloring:
```text
pupils: 1 2 3 4 5
edges : 1-2, 1-3, 4-5
component {1,2,3}: BFS from 1, team[1]=1
1 -> team 1
বন্ধু 2 -> team 2 ; বন্ধু 3 -> team 2
(1)team1
/ \
(2)t2 (3)t2 সব edge t1<->t2, conflict নেই
component {4,5}: BFS from 4, team[4]=1
4 -> team 1 ; বন্ধু 5 -> team 2
ফল: team = [_,1,2,2,1,2] (1-indexed) -> সম্ভব
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n = 3`, friendships `(1,2),(2,3),(3,1)` (বিজোড় চক্র):
1. `team = [0,0,0,0]` (index 0 অব্যবহৃত)। pupil 1-এর team নেই → `team[1] = 1`, BFS শুরু, queue `[1]`।
2. pop `1` → বন্ধু `2` (team নেই) → `team[2] = 3 - 1 = 2`, enqueue; বন্ধু `3` (team নেই) → `team[3] = 2`, enqueue।
3. pop `2` → বন্ধু `1` (team 1, দরকার `3 - 2 = 1` ✓); বন্ধু `3` (team 2, কিন্তু দরকার `3 - team[2] = 1`) → দ্বন্দ্ব! `team[3] = 2` অথচ 2-এর বন্ধু হিসেবে team 1 হওয়া উচিত।
4. return `IMPOSSIBLE`। (1-2-3 একটা 3-দৈর্ঘ্যের বিজোড় চক্র, তাই দুই team-এ ভাগ অসম্ভব।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def building_teams(n, edges):
# 1-indexed pupils; adjacency list বানাই
adj = [[] for _ in range(n + 1)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
team = [0] * (n + 1) # 0 = এখনো team নেই (visited-marker-ও বটে)
for start in range(1, n + 1): # disconnected: প্রতিটা component
if team[start] != 0:
continue
team[start] = 1
q = deque([start])
while q:
u = q.popleft()
for v in adj[u]:
if team[v] == 0: # team নেই -> উল্টো team
team[v] = 3 - team[u]
q.append(v)
elif team[v] == team[u]: # একই team পাশাপাশি -> দ্বন্দ্ব
return None
return team[1:] # index 1..n
def format_answer(n, edges):
res = building_teams(n, edges)
return "IMPOSSIBLE" if res is None else res
# ---- tests ----
assert format_answer(5, [(1, 2), (1, 3), (4, 5)]) == [1, 2, 2, 1, 2]
assert format_answer(3, [(1, 2), (2, 3), (3, 1)]) == "IMPOSSIBLE"
assert format_answer(3, []) == [1, 1, 1] # friendship নেই -> সবাই team 1
assert format_answer(2, [(1, 2)]) == [1, 2] # সরল এক edge
# bipartite property নিজে যাচাই: কোনো edge একই team-এ নেই
sol = building_teams(5, [(1, 2), (1, 3), (4, 5)])
for u, v in [(1, 2), (1, 3), (4, 5)]:
assert sol[u - 1] != sol[v - 1]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `adj = [[] for _ in range(n + 1)]` — 1-indexed adjacency list; index 0 ফাঁকা রাখি।
- `team = [0] * (n + 1)` — `0` দ্বৈত: team-হীন ও unvisited; team বসানোই visited-marking।
- `for start in range(1, n + 1): if team[start] != 0: continue` — disconnected graph-এর প্রতিটা component আলাদা শুরু।
- `team[v] = 3 - team[u]` — বন্ধুকে সবসময় উল্টো team; `3 - 1 = 2`, `3 - 2 = 1`।
- `elif team[v] == team[u]: return None` — already-assigned বন্ধু একই team-এ হলে ভাগ ভেঙে গেছে → `None` (পরে `IMPOSSIBLE`)।
- `return team[1:]` — index 1..n-এর team-গুলো, 0-indexed list হিসেবে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`format_answer(5, [(1,2),(1,3),(4,5)])`: component {1,2,3}-এ 1→team 1, 2→2, 3→2; component {4,5}-এ 4→1, 5→2; কোনো friendship একই team-এ নয় → `[1,2,2,1,2]`। দ্বিতীয়টায় 1-2-3 বিজোড় চক্র, edge 2-3 দুই একই-team pupil চায় → `IMPOSSIBLE`। তৃতীয়টায় friendship নেই, প্রতিটা pupil আলাদা component, সবাই team 1 → `[1,1,1]`। self-check loop প্রতিটা edge দুই আলাদা team-এ আছে যাচাই করে। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(V + E)** — প্রতিটা pupil একবার team পায় ও traverse হয়, প্রতিটা friendship constant-বার দেখা হয় (দুই প্রান্তের team তুলনা)। এখানে `V = n`, `E = m`।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V + E)** — adjacency list O(V + E), `team` array O(V), BFS queue worst case O(V)। CP-scale-এ এটাই সঠিক বাজেট।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- disconnected graph ভুলে যাওয়া — প্রতিটা pupil থেকে শুরুর বাইরের loop না দিলে কিছু component team-হীন থেকে যায়, ভুল উত্তর।
- CP-scale-এ recursive DFS চালিয়ে stack overflow করা — `n` 10^5 হলে deque-ভিত্তিক BFS নিরাপদ পছন্দ।
- already-assigned বন্ধুর team যাচাই না করা — শুধু team-হীন হলে রঙ দিলে দ্বন্দ্ব ধরা পড়ে না।
- 1-indexed pupils-এ array size `n` দেওয়া (`n + 1` দরকার) বা output-এ index 0 রেখে দেওয়া — off-by-one bug।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #11 Is Graph Bipartite?-এর two-coloring ([011-is-graph-bipartite.md](011-is-graph-bipartite.md)) আর তার তলার BFS/DFS traversal ([../bfs.md](../bfs.md), [../dfs.md](../dfs.md))। এটা সেই একই bipartite check, কিন্তু দুটো নতুন দাবি সহ: (১) CP scale, তাই adjacency list + deque, recursion নয়; (২) উত্তরে শুধু সম্ভব/অসম্ভব নয়, আসল team-assignment ছাপাতে হয়। মূল শিক্ষা একই — প্রতিবেশীকে উল্টো রঙ, একই রঙ পাশাপাশি = বিজোড় চক্র = অসম্ভব — কিন্তু এখানে রঙটাই deliverable। পরের ধাপ: traversal + একটা side-structure (copy map) নিয়ে #13।
### পরের অনুশীলন {#22-similar-harder-problems}
- Is Graph Bipartite? (একই two-coloring, ছোট scale) —