백준/1707번/Java - 이분 그래프

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

1707번: 이분 그래프

---

이분 그래프를 판별하는 방법을 알아야 하는 문제이다.

 

이분 그래프를 판별하기 위한 방법은 다음과 같다.

한 노드에서 시작하여 전체 노드를 탐색하며 처음 방문한 노드들을 번갈아가며 서로 다른 집합으로 분류한다.

갔던 노드를 다시 방문한 하는 경우, 다시 방문한 노드가 이전 노드와 같은 집합이라면 해당 그래프는 이분 그래프가 될 수 없으므로

탐색을 종료한다.

 

위의 탐색을 모든 노드에서 출발하는 경우에 다 해봐야 한다.

모든 노드가 다 연결되어 있다는 보장이 없기 때문이다.

 

따라서 모든 노드를 시작점으로 탐색을 하도록 반복문 내에서 dfs를 실행하되 한번이라도 이분 그래프가 될 수 없는 경우를 발견하면 더 이상 탐색을 할 필요가 없다.

 

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] team; // 0 or 1
    static boolean result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int K = Integer.parseInt(br.readLine());
        for(int i=0; i<K; i++) {
            //i번째 테스트 케이스
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken()); // 노드 개수
            int E = Integer.parseInt(st.nextToken()); // 간선 개수
            //노드 개수만큼 인접 리스트 초기화
            arr = new ArrayList[V+1];
            visited = new boolean[V+1];
            team = new int[V+1];
            for(int j=1; j<=V; j++) {
                arr[j] = new ArrayList<>();
            }
            //간선 개수 만큼 이어진 노드 정보 입력
            for(int j=0; j<E; j++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                arr[start].add(end);
                arr[end].add(start);
            }
            //데이터 세팅 끝
            //전체 그래프를 탐색하며 이분 그래프가 맞는 지 판별
            //방문했던 노드를 다시 방문하였을 때, 같은 집합에 속한 노드라면 이분 그래프가 될 수 없다.
            //그래프 전체를 탐색하기 위해 DFS.
            //모든 노드가 이어져있다는 보장이 없으므로 모든 노드에서 출발하는 경우를 다 따져봐야 함.
            result = true;

            for(int j=1; j<=V; j++) {
                if(result) {
                    dfs(j);
                }
            }
            if(result) {
                bw.write("YES\n");
            } else {
                bw.write("NO\n");
            }
        }


        br.close();
        bw.flush();
        bw.close();
    }

    private static void dfs(int node) {
        visited[node] = true;
        for(int i=0; i<arr[node].size(); i++) { //연결된 노드 탐색.
            int next = arr[node].get(i);
            if(!visited[next]) {
                //다음 노드가 방문하지 않은 노드라면, 집합을 분류하고 탐색
                if(team[node] == 0) team[next] = 1;
                else if(team[node] == 1) team[next] = 0;
                dfs(next);
            }
            else {
                //다음 노드가 방문한 노드라면 집합이 같은지 다른지 확인.
                //더 이상 탐색할 필요가 없음.
                if(team[node] == team[next]) {
                    result = false;
                    return;
                }
            }
        }
    }
}