G1707. 이분 그래프

문제

제출 코드

• 사용 알고리즘 : BFS

이분그래프의 “인접한 정점끼리는 같은 색으로 칠하지 않되, 총 두가지 색으로 칠해져야 함”이라는 특성을 이용해서, BFS로 그래프의 레벨별로 index(color)를 1씩 늘려가며 방문체크를 해주었다.

홀짝 여부에 따라 같은 집합에 속한 정점으로 판별하는 방식.

주어진 정점들이 모두 하나로 연결된 그래프라고 생각하고 풀었다가 틀렸었다.

package silver;

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

public class S14888_addOperator {

	static String bfs(int V, List<Integer>[] nodes) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int[] visit = new int[V+1];
		int color = 0;

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

			visit[i] = ++color;
			queue.add(i);

			while(!queue.isEmpty()) {
				color++;
				int size = queue.size();

				for(int s=0; s<size; s++) {
					int now = queue.poll();
					for(int node : nodes[now]) {
						if(visit[node] == 0) {
							visit[node] = color;
							queue.add(node);
						}else if(visit[node]!=color && visit[node]%2!=color%2) {
							return "NO";
						}
					}
				}
			}

		}
		return "YES";
	}

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

		for(int t=0; t<T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());

			List<Integer>[] nodes = new List[V+1];
			for(int i=1; i<=V; i++) nodes[i] = new ArrayList<Integer>();

			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				nodes[a].add(b);
				nodes[b].add(a);
			}

			System.out.println(bfs(V, nodes));
		}
	}

}