SPOJ 3916 "Bicolor" BICOLOR

問題：https://www.spoj.pl/problems/BICOLOR/

２彩色問題．
隣接する頂点をそれぞれ別の色で塗ることができるグラフかどうかを判定．

import java.util.*;

// 3916 bicolor BICOLOR 
public class Main {
	public static void main(String[] args) throws Exception {
		// 与えられたグラフが二色で彩色できるかどうか判定．
		for(int n;(n=next())>0;){
			int m = next();
			List<List<Integer>> adjList = new ArrayList<List<Integer>>();
			for (int i = 0; i <= n; ++i) {
				adjList.add(new ArrayList<Integer>());
			}
			for (int i = 0; i < m; ++i) {
				int a = next(), b = next();
				adjList.get(a).add(b);
				adjList.get(b).add(a);
			}
			int[] color = new int[n + 1]; // 色付け結果．
			// グラフが連結していない可能性があるため全ノード走査
			l:for (int i = 1; i <= n; ++i) {
				if (color[i] < 1) {
					// 連結している部分グラフをBFS
					Queue<Integer> q = new LinkedList<Integer>();
					q.add(i);
					color[i] = 1;
					while (!q.isEmpty()) {
						int u = q.poll();
						for (int v : adjList.get(u)) {
							// 一ヶ所でも「隣接ノードが同じ色」ならアウト
							if (color[v] > 0 && color[v] == color[u]) {
								System.out.print("NOT ");
								break l;
							} else if (color[v] < 1) {
								color[v] = 3 - color[u];
								q.add(v);
							}
						}
					}
				}
			}
			System.out.println("BICOLORABLE");
		}
	}

	static int next() throws Exception {
		int result = 0;
		int b = ' ';
		for (; b == '\n' || b == ' ';) {
			b = System.in.read();
		}
		for (; '0' <= b && b <= '9';) {
			result = result * 10 + b - '0';
			b = System.in.read();
		}
		return result;
	}
}