[백준 1707번] 이분 그래프

우선 이분 그래프가 정확히 뭔지 몰라 헷갈렸다.

 

이분 그래프란?

• 모든 정점을 두 가지 색으로 표현
• 인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결

 

 

처음에 문제를 풀 때 단순하게 싸이클 여부만 판단해서 풀었는데 6%에서 실패했다. 해당 그래프는 각각 독립적으로 두 개가 존재할 수도 있기 때문에 이러한 부분도 고려해야 한다.

 

 

 

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

public class BOJ_G4_1707_이분그래프 {
	static int[] p;
	static List<Integer>[] graphs;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		int K = Integer.parseInt(br.readLine());

		int V, E;
		while (K-- > 0) {
			st = new StringTokenizer(br.readLine());

			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());

			p = new int[V + 1];

			graphs = new List[V + 1];
			for (int i = 0; i < V + 1; i++) {
				graphs[i] = new ArrayList<>();
			}

			int a, b;
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());

				graphs[a].add(b);
				graphs[b].add(a);
			}

			boolean flag = false;
			for (int i = 1; i < V + 1; i++) {
				if (p[i] != 0) continue;
				if(!BFS(i)) {
					flag = true;
					break;
				}
			}
			if (!flag) sb.append("YES\n");
			else sb.append("NO\n");
		}


		System.out.println(sb);


	}

	static boolean BFS(int start) {
		ArrayDeque<Integer> q = new ArrayDeque<>();
		p[start] = 1;
		q.offer(start);

		while (!q.isEmpty()) {

			int curr = q.poll();

			for (Integer next : graphs[curr]) {
				if (p[next] == 0) {
					p[next] = -p[curr];
					q.offer(next);
				} else if (p[next] == p[curr]){
					return false;
				}
			}
		}

		return true;
	}
}