이분그래프

문제

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

YES
NO

풀이

간선 양 끝에 서로 다른 색을 줄 수 있는지 모든 연결 요소에서 검사한다. 이를 BFS로 구현한다.

간선을 사이에 두고 색을 바꾸기

이분 그래프라면 모든 간선의 양 끝은 서로 다른 집합에 속해야 한다. 한 정점에 색 1을 주고, 그 이웃에는 −1을 주는 식으로 BFS를 진행한다. 이미 색이 있는 이웃이 현재 정점과 같은 색이면 두 집합으로 나눌 수 없다. 예제의 두 번째 그래프에는 2→3→4→2의 홀수 길이 순환이 있어 색이 충돌한다.

그래프가 끊겨 있을 수도 있다. 시작 정점 하나에서만 검사하면 다른 연결 요소의 삼각형을 놓친다. 코드가 1번부터 V번까지 색이 없는 정점을 찾을 때마다 BFS를 새로 시작하는 이유다. 간선이 없는 정점은 어느 색에 두어도 되고, 자기 자신으로 연결된 간선은 즉시 색 충돌이 된다.

코드는 간선을 전부 읽은 뒤 판정하므로 실패를 발견해도 다음 테스트 케이스의 입력 위치가 어긋나지 않는다. 각 정점은 한 번 큐에 들어가고 무방향 간선은 양쪽에서 한 번씩 확인하므로 O(V+E) 시간, 인접 리스트·색 배열·큐에 O(V+E) 공간이 든다. 재귀 DFS도 가능하지만 V가 20,000인 경우 깊은 재귀가 스택 한도를 넘을 수 있어 BFS를 사용했다.

충돌을 더 작게 그리면 정점 세 개의 삼각형이다. 2를 색 1로 정하면 3과 4는 모두 −1이어야 한다. 그런데 3과 4 사이에도 간선이 있으므로 같은 색의 양 끝이 생긴다. 반대로 길이가 짝수인 순환은 색이 번갈아 돌아와 시작점과 모순되지 않는다. 이 성질 때문에 이분 그래프 판정은 홀수 길이 순환 검출과 연결된다.

검사 결과 NO가 났다고 입력의 나머지 간선을 읽지 않고 바로 다음 테스트 케이스로 넘어가면 입력이 뒤섞인다. 이 구현은 그래프를 완성한 뒤 BFS를 수행하므로 판정 중 조기 종료해도 다음 케이스를 온전히 읽는다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static boolean twoColor(List<List<Integer>> graph, int[] color, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        color[start] = 1;
        queue.add(start);
        while (!queue.isEmpty()) {
            int vertex = queue.remove();
            for (int next : graph.get(vertex)) {
                if (color[next] == 0) {
                    color[next] = -color[vertex];
                    queue.add(next);
                } else if (color[next] == color[vertex]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int cases = Integer.parseInt(in.readLine());
        StringBuilder out = new StringBuilder();
        while (cases-- > 0) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            int vertices = Integer.parseInt(st.nextToken());
            int edges = Integer.parseInt(st.nextToken());
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i <= vertices; i++) graph.add(new ArrayList<>());
            for (int i = 0; i < edges; i++) {
                st = new StringTokenizer(in.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            int[] color = new int[vertices + 1];
            boolean valid = true;
            for (int vertex = 1; vertex <= vertices; vertex++) {
                if (color[vertex] == 0 && !twoColor(graph, color, vertex)) {
                    valid = false;
                    break;
                }
            }
            out.append(valid ? "YES" : "NO").append('\n');
        }
        System.out.print(out);
    }
}