1707 이분 그래프

 

각 노드에 번호를 1, 2 번갈아가며 저장하면서, 인접 노드가 자신과 같은 번호일 경우 NO를, 아니면 YES를 출력한다.

     - 모든 노드 대해 DFS 실행한다! (이어져있지 않는 노드 잇을 수 잇기 때문)

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

public class Main {
    
    static int n;
    static boolean hasCycle;
    static List<List<Integer>> arr;
    static int[] sets;
    static boolean [] isVisited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            sets = new int[v + 1];
            isVisited = new boolean[v + 1];
            arr = new ArrayList<>();
            for (int j = 0; j <= v; j++) {
                arr.add(new ArrayList<>());
            }

            for (int j = 0; j < e; j++) {
                st = new StringTokenizer(br.readLine());

                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());

                arr.get(start).add(end);
                arr.get(end).add(start);
            }

            hasCycle = false;

            for (int k = 1; k <= v; k++) {
                if (hasCycle) break;
                else {
                    sets[k] = 1;
                    solution(k, 1);
                    sets = new int[v + 1];
                }

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

    static void solution(int currentPos, int currentSet) {
        if (hasCycle) return;

        isVisited[currentPos] = true;

        List<Integer> nextPosCandidates = arr.get(currentPos);
        int nextSet = 3 - currentSet; // 1 -> 2, 2 -> 1

        for (int nextPos : nextPosCandidates) {

            if (!isVisited[nextPos]) {
                sets[nextPos] = nextSet;
                solution(nextPos, nextSet);
            }

            else if (sets[nextPos] == sets[currentPos]) {
                hasCycle = true;
                break;
            }
        }
    }
}