[백준 1707 이분 그래프] - 파이썬 풀이 🦄

• 백준 1707 이분 그래프 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 1707 이분 그래프 - 파이썬 풀이 🦄

문제

2-Coloring을 하는 문제이다.

Keypoints

• 한 점에서 Color A로 시작해서 이웃한 노드는 다른 색깔을 칠하면 된다.
• 주의사항 : 모든 노드가 연결되지 않을 수 있으므로, 모든 점에서 시작해봐야 한다.

Solution

import sys 

def canBisect(graph, graph_linear, n):
    colors = [0 for i in range(n)]
    for v in range(n): #모든 점에서 확인
        if colors[v]==0:
            queue = [v]
            colors[v] = 1
            while queue:
                v = queue.pop(0)
                color = colors[v]
                for nei in graph[v]:
                    if colors[nei]==0:
                        colors[nei] = -color
                        queue.append(nei)

    for a,b in graph_linear:
        if colors[a] == colors[b]:
            return False
    return True

T = int(input())
for _ in range(T):
    v, e = map(int, map(int, sys.stdin.readline().strip().split()))
    graph = {i:[] for i in range(v)}
    graph_linear = []
    for i in range(e):
        a,b = map(int, map(int, sys.stdin.readline().strip().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        graph_linear.append((a-1,b-1))
    if canBisect(graph, graph_linear, v):
        print("YES")
    else:
        print("NO")

References

Problem Link