Skip to content

012 — Building Teams

Source

  • Original source: Classic bipartite two-coloring exercise (competitive-programming scale)
  • Platform: CSES Problem Set — https://cses.fi/problemset/task/1668
  • Topic: graphs
  • Difficulty: Medium
  • Pattern: bipartite coloring (CP scale)
  • Basic idea inherited from: bipartite check (011-is-graph-bipartite.md, এই tracker-এর #11); BFS levels (../bfs.md); DFS traversal (../dfs.md)

1. Problem in simple words

তোমার কাছে n জন pupil আর m টা "এরা দুজন বন্ধু" সম্পর্ক (edge) আছে। সবাইকে ঠিক দুটো team-এ ভাগ করতে হবে এমনভাবে, যাতে কোনো বন্ধু-জোড়া একই team-এ না পড়ে — প্রতিটা friendship যেন দুই team-এর মাঝে কাটা পড়ে। সম্ভব হলে প্রতিটা pupil-এর team (1 বা 2) ছাপাও; অসম্ভব হলে IMPOSSIBLE। এটা হুবহু #11-এর bipartite check, শুধু input বড় আর উত্তরে আসল রঙ-assignment চাই।

pupils 1..5, friendships: 1-2, 1-3, 4-5
team ভাগ: {1,4} -> team 1, {2,3,5} -> team 2
প্রতিটা friendship দুই team-এর মাঝে -> সম্ভব

2. Which basic idea does this inherit from?

মূল ভিত হলো #11-এর two-coloring আর তার তলায় থাকা BFS/DFS traversal (../bfs.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 ভাঙে না।

6. Real-life analogy

একটা বিতর্ক ক্লাব ভাবো যেখানে কিছু সদস্যের মধ্যে "এরা সবসময় বিপক্ষে দাঁড়ায়" সম্পর্ক আছে (edge)। তুমি সবাইকে দুটো দলে ভাগ করতে চাও যাতে প্রতিটা বিরোধী-জোড়া আলাদা দলে পড়ে, এক দলের ভেতরে কেউ কারো বিপক্ষ না থাকে। একজনকে দল A দাও, তার সব বিপক্ষকে দল B, তাদের বিপক্ষদের আবার দল A — ছড়াতে থাকো। যদি কখনো এমন কাউকে পাও যাকে আগেই দল দিয়েছ অথচ এখন তার উল্টো দল দরকার — দ্বন্দ্ব, এমন ভাগ অসম্ভব।

7. Visual explanation

n = 5, friendships 1-2, 1-3, 4-5 দিয়ে BFS coloring:

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) -> সম্ভব

8. Example input and output

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-এ দিলেই চলে)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা pupil-কে team 1 বা 2 দেওয়ার সব 2^n সমাবেশ ঘুরে দেখা, প্রতিটা assignment-এ যাচাই করা কোনো friendship একই team-এ পড়ছে কিনা।

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 বড় হলেও নিরাপদ।

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-এ ভাগ অসম্ভব।)

15. Python solution

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 হিসেবে।

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!।

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।

21. Which basic problem this inherits from

ভিত্তি: #11 Is Graph Bipartite?-এর two-coloring (011-is-graph-bipartite.md) আর তার তলার BFS/DFS traversal (../bfs.md, ../dfs.md)। এটা সেই একই bipartite check, কিন্তু দুটো নতুন দাবি সহ: (১) CP scale, তাই adjacency list + deque, recursion নয়; (২) উত্তরে শুধু সম্ভব/অসম্ভব নয়, আসল team-assignment ছাপাতে হয়। মূল শিক্ষা একই — প্রতিবেশীকে উল্টো রঙ, একই রঙ পাশাপাশি = বিজোড় চক্র = অসম্ভব — কিন্তু এখানে রঙটাই deliverable। পরের ধাপ: traversal + একটা side-structure (copy map) নিয়ে #13।

22. Similar harder problems

23. Pattern learned

Bipartite coloring (CP scale): "দুটো দলে এমন ভাগ যাতে প্রতিটা edge দুই দলের মাঝে" = traversal চালিয়ে প্রতিবেশীকে উল্টো রঙ দাও আর দ্বন্দ্ব খোঁজো; দ্বন্দ্ব = বিজোড় চক্র = অসম্ভব। বড় input-এ adjacency list + deque ব্যবহার করো, recursion এড়াও, আর disconnected হলে প্রতিটা component আলাদা করে রঙ করে actual assignment ফেরত দাও।

24. Final summary

ভবিষ্যতের আমাকে: "Building Teams = bipartite two-coloring, CP scale; deque দিয়ে BFS, বন্ধুকে 3 - team দাও, একই team পাশাপাশি পড়লেই IMPOSSIBLE; নাহলে assignment-টাই উত্তর।" যখনই 'দুই দলে ভাগ / কোনো জোড়া একসাথে নয় / conflict-free assignment' বড় scale-এ দেখবে — adjacency list + deque-তে রঙ ছড়াও, disconnected component ভুলো না, আর উত্তরে আসল রঙ ফেরত দাও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।