কনটেন্টে যান

011 — Is Graph Bipartite?

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা undirected graph দেওয়া আছে adjacency list হিসেবে — graph[u] হলো u-এর প্রতিবেশীদের list। বলো: এই graph কি bipartite? মানে, সব node-কে কি দুটো দলে (ধরো লাল ও নীল) এমনভাবে ভাগ করা যায়, যাতে প্রতিটা edge সবসময় এক লাল আর এক নীল node-কে জোড়ে — কখনো এক দলের ভেতরে edge না থাকে? পারলে True, না পারলে False। (graph disconnected হতে পারে।)

উদাহরণ
graph: 0-1, 1-2, 2-3, 3-0   (একটা 4-চক্র)
দল ভাগ: {0,2} লাল, {1,3} নীল  -> প্রতিটা edge দুই রঙের মাঝে -> True

Input ও output

উদাহরণ
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)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো BFS layer-by-layer expansion (../bfs.md) আর DFS traversal (../dfs.md)। BFS-এ even layer-গুলো এক রঙ, odd layer-গুলো অন্য রঙ দিলেই two-coloring তৈরি হয়ে যায় — কারণ প্রতিটা edge পাশাপাশি দুই layer-কে জোড়ে। DFS-এ একই কাজ: একটা node রং করো, প্রতিটা প্রতিবেশীকে উল্টো রঙ দাও। তাই এটা চেনা traversal-এর উপর শুধু একটা "color" বসানো — নতুন কোনো algorithm নয়।

ভেতরের যুক্তি

লুকানো logic: একটা graph bipartite তখনই, যখন তাতে কোনো odd-length cycle নেই। two-coloring-এ প্রতিবেশীকে সবসময় উল্টো রঙ দিতে চাও; কোনো cycle-এর দৈর্ঘ্য জোড় হলে রং পরিষ্কারভাবে আবার মেলে, বিজোড় হলে কোথাও দুই একই-রঙ node পাশাপাশি পড়ে যায় — তখন bipartite অসম্ভব। তাই traversal চালিয়ে প্রতিটা node-কে প্রতিবেশীর উল্টো রঙ দাও; যদি কখনো এমন প্রতিবেশী পাও যাকে আগেই একই রঙ দেওয়া হয়েছে — conflict, return False। কোনো conflict ছাড়া সব রং করা গেলে True।

কী দিয়ে তথ্য রাখব

  • adjacency list (input-ই) — প্রতিটা node-এর প্রতিবেশী।
  • color array/map — প্রতিটা node-এর রং: -1 (অরঙা), 0, বা 1।
  • collections.deque (BFS) বা recursion stack (DFS) — graph traverse করতে।
  • disconnected handling — প্রতিটা node থেকে একবার শুরু করার জন্য বাইরের loop।

এটি কেন উপযুক্ত

Color array fit করে কারণ দুটো দল মানে দুটো মান (0/1), আর 1 - color দিয়ে তাৎক্ষণিক উল্টো রঙ পাওয়া যায়; -1 দিয়ে "এখনো রঙ হয়নি" বোঝে, তাই আলাদা visited লাগে না (রঙ থাকা = visited)। BFS/DFS দুটোই fit করে কারণ bipartite-চেক structural — distance নয়, রঙের সঙ্গতি; তাই যেকোনো traversal চলে। বাইরের loop fit করে কারণ graph disconnected হতে পারে, প্রতিটা component আলাদা করে রং করা দরকার।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: সব সম্ভাব্য দুই-দলে ভাগ চেষ্টা করে দেখা — প্রতিটা node-কে দল A বা B দেওয়ার সব 2^n সমাবেশ ঘুরে, প্রতিটা assignment-এ যাচাই করা সব edge দুই দলের মাঝে পড়ছে কিনা।

উদাহরণ
1) প্রতিটা node-কে A/B দেওয়ার প্রতিটা সম্ভাব্য combination নাও
2) সেই combination-এ সব edge চেক করো — দুই প্রান্ত আলাদা দলে?
3) কোনো combination সব edge পাস করালে True; কোনোটাই না করালে False

কোথায় বেশি কাজ হচ্ছে

2^n assignment ঘুরে দেখা exponential — সামান্য বড় graph-এও অসম্ভব। অথচ রঙ আসলে স্বাধীন নয়: একটা node-এর রঙ ঠিক হলে তার প্রতিবেশীদের রঙ বাধ্যতামূলকভাবে উল্টো — কোনো পছন্দই নেই। তাই একটা traversal-এ রঙ "ছড়িয়ে" দিলেই হয়, আর শুধু দেখো কোথাও দ্বন্দ্ব হয় কিনা — O(V + E)। সব combination চেষ্টা করা পুরোপুরি অপচয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা node-এর রঙ স্থির হলে তার সব প্রতিবেশীর রঙ বাধ্যতামূলক (উল্টো)। তাই কোনো পছন্দ বা search নেই — শুধু একটা node থেকে রঙ ছড়িয়ে দাও, আর প্রথম যেখানে দুই একই-রঙ প্রতিবেশী পাশাপাশি পড়ে, সেখানেই bipartiteness ভেঙে যায়।

আরও কম কাজে সমাধান

color array -1-এ শুরু। প্রতিটা node থেকে (disconnected-এর জন্য) — যদি অরঙা থাকে — তাকে রঙ 0 দিয়ে BFS/DFS শুরু করো। traversal-এ প্রতিটা প্রতিবেশীর জন্য: অরঙা হলে 1 - color[cur] দাও আর এগোও; ইতিমধ্যে রঙ থাকলে সেটা 1 - color[cur] কিনা যাচাই করো — না হলে (একই রঙ) return False। সব component দ্বন্দ্ব ছাড়া রঙ হলে True। O(V + E)।

ভাবনার পরিবর্তন

মোচড়: "সব রকম দুই-দলে ভাগ চেষ্টা করব" না ভেবে ভাবো "একটা রঙ ঠিক করলে বাকি সব রঙ নিজে থেকেই ঠিক হয়ে যায় — শুধু traverse করে দ্বন্দ্ব খুঁজি।" search থেকে নেমে এসো একটা rng-ছড়ানো traversal-এ, যেখানে প্রতিবেশী সবসময় উল্টো রঙ।

ছবিতে বোঝা

graph = [[1,3],[0,2],[1,3],[0,2]] (4-চক্র 0-1-2-3-0) দিয়ে BFS coloring:

উদাহরণ
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-এ ধাপে ধাপে

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 নয়।)

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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

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

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<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]]), true, "even-cycle");
expect(isBipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]), false, "odd-cycle");
expect(isBipartite([[], [], []]), true, "no-edge");
console.log("সব TS test pass!");

TS টীকা: input-কে number[][] (adjacency list) declare করায় ভুল আকৃতির graph (যেমন string[][]) compile-time-এই ধরা পড়ে; color: number[] রাখায় ভুলে অন্য type মেশানো যায় না, আর return type boolean ফাংশনের contract পরিষ্কার করে।

খরচ ও সাধারণ ভুল

সময়

O(V + E) — প্রতিটা node একবার রঙ ও traverse হয়, প্রতিটা edge constant-বার দেখা হয় (দুই প্রান্তের রঙ তুলনা)।

অতিরিক্ত জায়গা

O(V) — color array O(V), আর BFS queue / DFS recursion stack worst case O(V)। (adjacency list input, তাই গোনা হয় না।)

যে ভুলগুলো এড়াতে হবে

  • disconnected graph ভুলে যাওয়া — প্রতিটা node থেকে শুরু করার বাইরের loop না দিলে কিছু component অরঙা থেকে যায়, ভুল উত্তর।
  • already-রঙা প্রতিবেশীর রঙ যাচাই না করা — শুধু অরঙা হলে রঙ দিলে দ্বন্দ্ব ধরা পড়ে না।
  • visited আর color আলাদা রাখার চেষ্টা করে গোলমাল — color -1 নিজেই visited-marker, একটাই array যথেষ্ট।
  • self-loop থাকা graph-এ ভাবনা না রাখা — একটা node নিজের সাথে edge থাকলে কখনোই bipartite নয় (যদিও সাধারণ input-এ থাকে না)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: BFS layer-expansion (../bfs.md) ও DFS traversal (../dfs.md)। এটা চেনা traversal-এর উপর একটা "color" বসানোর প্রথম problem — দূরত্ব বা component নয়, রঙের সঙ্গতি যাচাই। মূল নতুন শিক্ষা: traversal-এর সময় প্রতিটা node-এ একটা label/state বইয়ে নিয়ে গিয়ে constraint যাচাই করা যায় — এই two-coloring কৌশল আর "বিজোড় চক্র = bipartite নয়" সত্যটা পরে অনেক জায়গায় ফিরে আসে। পরের ধাপ: একই bipartite coloring কিন্তু CP scale-এ (#12)।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Two-coloring / bipartite check: "দুটো দলে এমন ভাগ করা যায় কিনা যাতে প্রতিটা edge দুই দলের মাঝে" = traversal চালিয়ে প্রতিবেশীকে উল্টো রঙ দাও আর দ্বন্দ্ব খোঁজো; দ্বন্দ্ব = বিজোড় চক্র = bipartite নয়। BFS/DFS দুটোই চলে, খরচ O(V + E)। disconnected হলে প্রতিটা component আলাদা করো।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "bipartite = two-coloring; প্রতিবেশীকে উল্টো রঙ দাও, একই রঙ পাশাপাশি পড়লেই False; বিজোড় চক্র থাকলে অসম্ভব।" যখনই 'দুই দলে ভাগ / কোনো edge এক দলে নয় / conflict-free assignment' দেখবে — traversal-এর সাথে রঙ বইয়ে নাও, আর disconnected component-এর কথা ভুলো না।

কোথায় কাজে লাগে

  • Scheduling / conflict graph: যেসব কাজ বা পরীক্ষা একসাথে চালানো যাবে না (edge = conflict) — তাদের দুই slot/দুই room-এ ভাগ করা সম্ভব কিনা bipartite-check বলে দেয়।
  • Job assignment / matching: worker ও task দুই দলে — bipartite হলেই maximum bipartite matching (কে কোন কাজ পাবে) চালানো যায়; এটাই assignment-এর ভিত।
  • Stable two-team split: খেলোয়াড়দের "প্রতিদ্বন্দ্বী" সম্পর্ক ধরে দুই দলে ভাগ (যেমন এই tracker-এর Building Teams) — same-team conflict ছাড়া।
  • Hardware / VLSI placement: দুই-স্তরের তারে component বসানো যাতে কোনো তার একই স্তরে cross না করে — two-colorability যাচাই।
  • Type/constraint consistency: "A আর B আলাদা শ্রেণিতে" জাতীয় constraint-এর সেট পরস্পরবিরোধী (odd cycle) কিনা দ্রুত ধরা।

মূল pattern: "দুই দলে এমন ভাগ যাতে কোনো edge এক দলে নয়" দেখলেই two-coloring; odd cycle থাকলে অসম্ভব।

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