<java> 백준 1707 이분 그래프

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

1707번: 이분 그래프

---

---

import java.util.*;
import java.awt.AlphaComposite;
import java.io.*;
public class Main {
	static ArrayList<Integer> al[];
	static int[] check;
	static Queue<Integer> q;
	static int v;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int k = Integer.parseInt(br.readLine());
		while(k --> 0) {
			st = new StringTokenizer(br.readLine());
			v = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			q = new ArrayDeque<>();
			al = new ArrayList[v + 1];
			for (int i = 0; i <= v; i++) {
				al[i] = new ArrayList<>();
			}
			check = 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());
				al[a].add(b);
				al[b].add(a);
			}
			if(bfs())
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
	public static boolean bfs() {
		for (int j = 1; j <= v; j++) {
			if (check[j] != 0)
				continue;
			q.add(j);
			check[j] = 1;
			while(!q.isEmpty()) {
				j = q.poll();

				for (int i = 0; i < al[j].size(); i++) {
					int b = al[j].get(i);
					if (check[b] == 0) {
						q.add(b);
						if (check[j] == 1)
							check[b] = 2;
						else
							check[b] = 1;
					}
					else if (check[b] == check[j]) {
						return false;
					}
				}
			}
		}
		return true;
	}
}

---