[백준] 이분 그래프(골드4)

문제 링크 

https://www.acmicpc.net/problem/7569

 

이분 그래프(Bipartite Graph)의 정의

- 정점을 두 그룹으로 나눌 수 있는 그래프

- 이분 그래프가 될 수 있는 조건: 같은 그룹 안에는 간선이 없어야함

- 즉 모든 간선은 다르 그룹을 연결

 

예시

그룹 1: {A, B}
그룹 2: {C, D}
간선: A-C, A-D, B-C, B-D
→ 가능 ✅

간선: A-B
→ A와 B가 같은 그룹 → ❌

bfs 이용 문제

- is_bipartite 함수에서 전체 for 문을 도는 이유: 그래프가 연결 그래프가 아닐 수도 있기 때문에 <- 만약 연결 그래프라는 보장이 있으면 굳이 for문 돌 필요 x 

- bfs 구현 코드

- 인접 노드들을 모두 돌면서 아직 방문하지 않은 노드인 경우 현재 노드의 반대 색깔을 적용

- 만약 방문한 노드인데 현재 노드와 색이 같은 경우 -> 바로 return False

 

구현 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start, graph, color):
    q = deque([start])
    color[start] = 1

    while q:
        v = q.popleft()
        for nxt in graph[v]:
            if color[nxt] == 0:
                color[nxt] = -color[v]
                q.append(nxt)
            elif color[nxt] == color[v]:
                return False
    return True

def is_bipartite(v, graph):
    color = [0] * (v + 1)
    for i in range(1, v+1):
        if color[i] == 0:
            if not bfs(i, graph, color):
                return False
    return True

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    print("YES" if is_bipartite(v, graph) else "NO")