220303 - 이분 그래프

◾ 이분 그래프 : 백준 1707번

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

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

---

입력

• 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다.
• 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

• K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

입출력 예

Input	Output
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO

---

◾ 풀이

1. 해설

• BFS를 통해 각 정점의 그룹을 구해간다.
  • dict형을 통해 각 정점을 0, 1, -1로 구분한다.
  • 0 : 미방문, 1 : 그룹 1, -1 : 그룹 -1
  • 서로 인접하지 않게 분리하기 위해 특정 정점에 대해 인접 정점은 해당 그룹의 반대 그룹으로 할당한다.
  • 만약 특정 정점과 인접 정점의 그룹이 같다면 이분 그래프로 만들 수 없음을 의미한다.

---

2. 프로그램

1. k(테스트 케이스) 입력
2. v(정점의 수), e(간선의 수) 입력
3. edges, visited, flag 초기화
4. edges 입력
5. 각 정점을 기준으로 BFS 알고리즘 실행
   • 시작 정점의 그룹 1
   • 인접 정점의 그룹 : 해당 정점의 그룹 * (-1)
   • 인접 정점과 해당 정점의 그룹이 같은 경우 False 반환

# 코드
import sys
from collections import deque
input = sys.stdin.readline

k = int(input())

for _ in range(k):
    v, e = map(int, input().split(' '))
    edges = {i : [] for i in range(1, v+1)}
    visited = {i : 0 for i in range(1, v+1)}
    flag = True

    for __ in range(e):
        v1, v2 = map(int, input().split(' '))
        edges[v1].append(v2)
        edges[v2].append(v1)

    for v_ in range(1, v+1):
        if visited[v_] == 0 :
            points = deque([])
            points.append(v_)
            visited[v_] = 1
            while points:
                v_ = points.popleft()
                for new_v in edges[v_]:
                    if visited[new_v] == 0:
                        points.append(new_v)
                        visited[new_v] = -visited[v_]
                    else:
                        if visited[new_v] == visited[v_]:
                            flag = False
                            break
            if flag == False :
                break
    
    if flag:
        print("YES")
    else:
        print("NO")

• Input
  2
  3 2
  1 3
  2 3
  4 4
  1 2
  2 3
  3 4
  4 2