[Java] 백준 1707 - 이분 그래프

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

---

풀이

각 노드마다 1과 -1을 번갈아 매기면서 그래프 탐색 (BFS/DFS):

1이 들어가야할 노드에 이미 -1이 들어가있으면 NO

-1이 들어가야할 노드에 이미 1이 들어가있으면 NO

별 문제없이 그래프 탐색이 끝나면 YES

---

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		outerLoop: 
        	while (K-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			ArrayList<ArrayList<Integer>> edges = new ArrayList<>();

			for (int i = 0; i < V + 1; i++) {
				edges.add(new ArrayList<>());
			}
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				edges.get(u).add(v);
				edges.get(v).add(u);
			}

			int[] color = new int[V + 1];

			for (int i = 1; i <= V; i++) {
				if (color[i] == 0) {
					color[i] = 1;

					Queue<Integer> que = new LinkedList<>();
					que.add(i);

					while (!que.isEmpty()) {
						int cur = que.remove();

						for (int dest : edges.get(cur)) {
							if (color[dest] == color[cur]) {
								sb.append("NO\n");
								continue outerLoop;
							}

							if (color[dest] == 0) {
								color[dest] = color[cur] * -1;
								que.add(dest);
							}
						}
					}
				}
			}
			sb.append("YES\n");
		}

		System.out.println(sb);
		br.close();
	}
}