← 15주차 · 그래프와 DFS · BFS
어려움그래프BFSDFS

이분 그래프 판별

정점 개수 n과 간선 목록 edges로 이루어진 무방향 그래프가 주어져요. 정점은 0번부터 n-1번까지 있어요.

모든 정점을 두 가지 색으로 칠하되, 간선으로 이어진 두 정점은 항상 색이 다르게 만들 수 있으면 그 그래프는 이분 그래프예요. 이분 그래프면 true, 아니면 false를 반환해요.

탐색하면서 색을 칠하면 돼요. 시작 정점을 한 색으로 칠하고, 이웃은 반대 색으로 칠해요. 칠하려는 이웃이 이미 같은 색으로 칠해져 있으면 이분 그래프가 아니에요. 그래프가 여러 덩어리로 나뉘어 있을 수 있으니 모든 정점에서 확인해요.

예시

예시 1
입력
n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
출력
true
설명
0·2를 한 색, 1·3을 다른 색으로 칠하면 돼요(짝수 길이 사이클).
예시 2
입력
n = 3, edges = [[0, 1], [1, 2], [2, 0]]
출력
false
설명
삼각형(홀수 길이 사이클)은 두 색으로 칠할 수 없어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 200,000
  • 0 ≤ a, b < n, self-loop는 없어요.
color 배열을 0(안 칠함)으로 두고, 아직 안 칠한 정점마다 BFS를 시작해요. 시작 정점을 1로 칠하고, 이웃이 안 칠해졌으면 반대 색(3 - 현재색)으로 칠해 큐에 넣어요. 이웃이 이미 현재 정점과 같은 색이면 바로 false예요.
javascript
function bipartiteCheck(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const color = new Array(n).fill(0);
  for (let s = 0; s < n; s++) {
    if (color[s] !== 0) continue;
    color[s] = 1;
    const queue = [s];
    let head = 0;
    while (head < queue.length) {
      const v = queue[head++];
      for (const next of graph[v]) {
        if (color[next] === 0) {
          color[next] = 3 - color[v];
          queue.push(next);
        } else if (color[next] === color[v]) {
          return false;
        }
      }
    }
  }
  return true;
}
이전 문제섬의 개수
다음 문제미로 최단 거리
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.