코드

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

class Main {
    private static List<List<Integer>> graph;
    private static int[] colors;
    private static final int RED = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());

        for (int t = 0; t < K; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            graph = new ArrayList<>();
            colors = new int[N + 1];

            for (int i = 0; i <= N; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());
                graph.get(node1).add(node2);
                graph.get(node2).add(node1);
            }

            boolean isBipartite = true;
            for (int i = 1; i <= N; i++) {
                if (colors[i] == 0) {
                    if (!isBipartiteGraph(i, RED)) {
                        isBipartite = false;
                        break;
                    }
                }
            }

            System.out.println(isBipartite ? "YES" : "NO");
        }
    }

    private static boolean isBipartiteGraph(int start, int color) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        colors[start] = color;

        while (!q.isEmpty()) {
            int current = q.poll();
            for (int next : graph.get(current)) {
                if (colors[next] == colors[current]){
	                return false;
                } 
                if (colors[next] == 0) {
                    colors[next] = -colors[current];
                    q.add(next);
                }
            }
        }

        return true;
    }
}

Java에서 List<List<Integer>> graph가 쓰이는 이유는 바로 그래프의 인접 리스트 (adjacency list) 표현 때문이에요.

이건 이 문제, 백준 1707번 **"이분 그래프(Bipartite Graph)"**를 효율적으로 해결하기 위한 가장 일반적인 방법이에요.

왜 List<List<Integer>> 인가?

간단히 말해서:

List<List<Integer>> graph;

이건 "정점마다 연결된 정점 리스트를 담는 리스트", 즉 2차원 리스트에요.

예를 들어,

• graph.get(0)는 0번 정점과 연결된 정점들의 리스트

• graph.get(1)은 1번 정점과 연결된 정점들의 리스트

  ... 이런 식이에요.

예시

입력: