백준 1707번 이분 그래프

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q48p269BaekJoon1707 {

	private static ArrayList<Integer>[] list;
	private static Queue<Integer> qu = new ArrayDeque<>();
	private static int nodes=0;
	private static int edges=0;
	private static int testCase =0;
	private static int check[]=null;
	private static BufferedWriter bw;
	
	public static void main(String[] args) throws IOException {
		BufferedReader buf =new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		testCase=Integer.parseInt(buf.readLine());
		
		
		for(int test=0;test<testCase;test++) {
			st =new StringTokenizer(buf.readLine());
			nodes = Integer.parseInt(st.nextToken());
			edges =Integer.parseInt(st.nextToken());
			
			if(nodes == 1) {
				bw.write("YES"+"\n");
				continue;
			}

			list = new ArrayList[nodes+1];
			for(int i=1;i<=nodes;i++) {
				list[i]=new ArrayList<>();
			}
			
			for(int i=0; i<edges;i++) {
				st = new StringTokenizer(buf.readLine());
				int x =Integer.parseInt(st.nextToken());
				int y =Integer.parseInt(st.nextToken());
				list[x].add(y);
				list[y].add(x);
			}

			check = new int[nodes+1];
			
			boolean isBipartite = true;
			for (int i = 1; i <= nodes; i++) {
				if (check[i] != 0) continue;
				isBipartite = isBipartite && isBipartite(i);
				if (!isBipartite) break;
			}
			bw.write(isBipartite ? "YES\n" : "NO\n");
		}
		bw.flush();
	}

	private static boolean isBipartite(int start) throws IOException {
		qu.clear();
		qu.add(start);
		check[start] = 1;
		while(!qu.isEmpty()) {
			int crnt = qu.poll();
			for(int next : list[crnt]) {
				if(check[next] != 0) {
					if (check[next] == check[crnt]) return false;
					continue;
				}
				check[next] = check[crnt] == 1 ? 2 : 1;
				qu.add(next);
			}
		}
		return true;
	}

}