[Baekjoon Online Judge] 1707 - 이분 그래프 / Java

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

1707번: 이분 그래프

// 이분 그래프(bipartite graph)
// : 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나누어서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프
// : ex) 검은색 정점, 흰색 정점
//		: 검은색 정점들 간에는 간선 없음 => 같은 색(레벨)은 간선 없음
//		: 인접한 정점은 색이 달라야 함

// 그래프의 꼭짓점들을 깊이 우선 탐색으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서,
// 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다.


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	final static int BLACK = -1;
	final static int WHITE = 1;
	static int[] colors; // black = -1, white = 1, 방문하지 않은 정점: 0
	static boolean isBipartiteGraph;
	static Node[] list;

	static class Node {
		int vertex;
		Node link;

		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int K = Integer.parseInt(st.nextToken()); // 테스트케이스 수
		for (int testCase = 1; testCase <= K; testCase++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken()); // 정점의 개수
			int E = Integer.parseInt(st.nextToken()); // 간선의 개수

			list = new Node[V + 1];
			colors = new int[V + 1];

			for (int e = 0; e < E; e++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				list[from] = new Node(to, list[from]);
				list[to] = new Node(from, list[to]);
			}
            
            		// 모든 정점 탐색
			isBipartiteGraph = true;
			for (int i = 1; i <= V; i++) {
				if (!isBipartiteGraph) {
					break;
				}

				if (colors[i] == 0) {
					dfs(i, BLACK);
				}
			}
			sb.append(isBipartiteGraph ? "YES" : "NO").append("\n");
		}
		System.out.println(sb);
	}

	static void dfs(int current, int color) {
		colors[current] = color; // visit

		for (Node temp = list[current]; temp != null; temp = temp.link) {
			if (colors[temp.vertex] == color) {
				isBipartiteGraph = false;
				return;
			}

			// 아직 방문하지 않은 정점이면 현재 색과 다른 색으로 저장
			if (colors[temp.vertex] == 0) {
				dfs(temp.vertex, (color == BLACK ? WHITE : BLACK));
			}
		}
	}
}