[백준] 1707 이분 그래프 [자바]

 

---

https://jellyinghead.tistory.com/14

[백준 1707] 이분 그래프 (자바)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
	static ArrayList<Integer>[] list;
	static int[] visit;
	static int V;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine());
 			V = Integer.parseInt(st.nextToken());
 			int E = Integer.parseInt(st.nextToken());
 			list = new ArrayList[V+1];
 			for(int i = 0; i <= V; i++) {
 				list[i] = new ArrayList<Integer>();
 			}
 			visit = new int[V+1];
 			for(int i = 0; i < E; i++) {
 				st = new StringTokenizer(br.readLine());
 				int a = Integer.parseInt(st.nextToken());
 				int b = Integer.parseInt(st.nextToken());
 				list[a].add(b);
 				list[b].add(a);
 			}
 			if(bfs()) {
 				System.out.println("YES");
 			}
 			else {
 				System.out.println("NO");
 			}
 		}
 	}
 	static boolean bfs() {
 		LinkedList<Integer> que = new LinkedList<>();
 		for(int i = 1; i <= V; i++) {
 			if(visit[i] == 0) {
 				que.add(i);
 				visit[i] = 1; //초
 			}
 			while(!que.isEmpty()) {
 				int now = que.poll();
 				for(int j = 0; j < list[now].size(); j++) {
 					if(visit[list[now].get(j)] == 0) {
 						que.add(list[now].get(j));
 					}
 					if(visit[list[now].get(j)] == visit[now]) {
 						return false;
 					}
 					if(visit[now] == 1 && visit[list[now].get(j)] == 0) {
 						visit[list[now].get(j)] = 2;
 					}
 					else if(visit[now] == 2 && visit[list[now].get(j)] == 0) {
 						visit[list[now].get(j)] = 1;
 					}
 				}
 			}
 		}
 		return true;
 	}
}