1707_이분 그래프

사용 알고리즘: bfs

사용 언어: java

 

package di_8_1_그래프의표현;

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

public class Main_bj_1707_이분그래프 {
	static int v, e, redBlack[];
	static List<Integer>[] al;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		for(int t=0; t<tc; t++) {
			v = sc.nextInt();
			e = sc.nextInt();
			
			al = new ArrayList[v];
			for (int i = 0; i < v; i++) {
				al[i] = new ArrayList<>();
			}
			
			for (int i = 0; i < e; i++) {
				int a = sc.nextInt()-1;
				int b = sc.nextInt()-1;
				al[a].add(b);
				al[b].add(a);
			}
			
			boolean binary = true;
			redBlack = new int[v];
			for(int i=0; i<v; i++) {
				if(redBlack[i] == 0) {
					redBlack[i] = 1;
					boolean subbinary = bfs_1707(i);
					if(!subbinary) {
						binary = false;
						break;
					}
				}
			}
			
			if(binary) System.out.println("YES");
			
//			System.out.println(Arrays.toString(redBlack));
		}
	}

	private static boolean bfs_1707(int start) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(start);
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			int red = redBlack[cur];
			
			for(int nxt : al[cur]) {
				if(redBlack[nxt] == 0) {
					q.add(nxt);
					redBlack[nxt] = -red;
				} else {
					if(red == redBlack[nxt]) {
						System.out.println("NO");
						return false;
					}
				}
			}
		}
		
//		System.out.println("YES");
		return true;
	}

}

 

문제를 읽다 보니, 이거 레드블랙 트리가 이런 느낌 아닌가?? 싶었다. (맞나?)

 

처음엔 모든 정점이 연결되어 있는 입력만 들어오는 줄 알았는데, 그렇지 않은 입력도 있어서 틀림.

boolean 변수를 사용해서 해결했다.