백준 1707: 이분 그래프

문제 요약

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

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS
• 이분 그래프

문제 풀이

이분 그래프는 인접한 정점끼리는 서로 같은 집합에 속하지 않도록 했을 때 정확히 두 집합으로 나눌 수 있는 그래프를 말한다.
여기서 이분 그래프는 홀수 사이클이 존재하는가의 여부를 통해 판별할 수 있다. 그래프에서 홀수 사이클이 발견된다면, 인접 정점을 서로다른 두 집합으로 나누는 것이 불가능하다. 다만, 짝수 사이클의 경우에는 가능하다.

각 정점을 방문할 때마다 번호를 부여하여, 집합에 할당한다. 여기서는 boolean형의 true나 false로 배정한다. 다음에 탐색할 노드가 이미 방문했으면서, 자신과 배정된 번호가 같다면 이분그래프가 아니다.

풀이 코드

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

public class Main {
	static int n, m;
	static List<Integer>[] edge;
	static boolean visited[];
	static boolean nodeNum[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        int v, u;
        while(T-- > 0) {
        	st = new StringTokenizer(br.readLine());
        	n = Integer.parseInt(st.nextToken());
        	m = Integer.parseInt(st.nextToken());
        	edge = new List[n + 1];
        	for(int i = 1; i <= n; i++)
        		edge[i] = new ArrayList<>();
        	visited = new boolean[n + 1];
        	nodeNum = new boolean[n + 1];
        	
        	while(m-- > 0) {
        		st = new StringTokenizer(br.readLine());
        		v = Integer.parseInt(st.nextToken());
        		u = Integer.parseInt(st.nextToken());
        		edge[v].add(u);
        		edge[u].add(v);
        	}
        	boolean flag = false;
        	for(int i = 1; i <= n; i++) {
        		if(!visited[i]) {
        			flag = dfs(i, false);
        			if(flag) break;
        		}
        	}
        	if(flag) sb.append("NO\n");
        	else sb.append("YES\n");
        }
        System.out.print(sb);
    }
    
    static boolean dfs(int idx, boolean b) {
    	visited[idx] = true;
    	nodeNum[idx] = b;
    	boolean ret = false;
    	for(int it : edge[idx]) {
    		if(!visited[it])
    			ret = dfs(it, !b);
    		else if(b == nodeNum[it])
    			return true;
    	}
    	return ret;
    }
}