[백준] 1707번 : 이분 그래프

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

1707번: 이분 그래프

해당 문제는 이분 그래프의 성질을 알야아 풀 수 있는 문제입니다.

이분 그래프는 그래프 형태의 자료구조인데 정점을 2 그룹으로 나누었을때 같은 그룹의 정점끼리 간선이 없을 경우를 이분 그래프 라고 합니다. 아래의 그림과 같이 표현 할 수 있습니다.

빨간색 정점들과 파란색 정점들이 연결되어있는 상태로 파란색 정점들끼리 연결이 되어있지 않는상태, 빨간색 정점들끼리 연결되어있지 않는 상태 입니다.

간선이 아예 없고 정점만 있는 경우도 이분그래프 입니다.

 

탐색을 할때 정점을 그룹화 하고 같은 그룹의 정점이 만났을때 이분그래프가 아니니 No를 출력하고 모든 간선을 다 방문 했는데도 같은 그룹의 정점이 만나지 않는다면 Yes를 출력 하면 됩니다.

 

그룹을 1과 -1로 나누어 그룹핑을 하고 만약 간선들을 방문하다가 그룹이 같은 그룹이 연결되어진 간선정보가 나온다면 이분 그래프가 아니므로 False로 변환후 종료한다.

from collections import deque

K = int(input()) # 테스트 케이스


for _ in range(K):
    V, E = map(int, input().split()) # 정점의 개수, 간선의 개수
    visisted = [False for _ in range(V+1)]
    graph = [[] for _ in range(V+1)] # 해당 정점에서 다른정점까지의 가는 경로 정보 저장 그래프
    for _ in range(E):
        start, end = map(int, input().split())
        graph[end].append(start)
        graph[start].append(end)
    

        
    # 너비 우선 탐색
    isbinaryGraph = True
    for i in range(V+1):
        queue = []
        if not visisted[i]: # 그룹이 지정되어있지 않다면
            queue = deque([i])
            visisted[i] = 1 # 그룹을 지정한다.
        while queue: # 해당 Queue는 만약 i가 1이라면 1과 연결된 모든 정점의 정보들을 그룹 -1,1로 나눈다.
            x = queue.popleft() # 정점을 pop 한다.
            for v in graph[x]:
                if not visisted[v]:
                    queue.append(v)
                    visisted[v] = -1 * visisted[x] # -1 그룹 생성
                elif visisted[v] == visisted[x]: # 그룹이 같다면 
                    isbinaryGraph = False
                    break
    if isbinaryGraph:
        print("YES")
    else:
        print("NO")