048 : Bipartite graph 판별하기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
	순환 > 이분그래프 X	테스트 케이스 갯수 K 노드 수 V, 에지 수 E (1)노드 - 노드(단방향 연결 정보) ... (E)노드 - 노드 O// YES or No

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    // Preprocessing
    static ArrayList<Integer>[] A;
    static int[] check;
    static boolean visited[];
    static boolean isEven;

    public static void main(String[] args) throws Exception {

        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        
        // Preprocessing
        for (int t = 0; t < N; t++) {
            String[] s = br.readLine().split(" ");
            int V = Integer.parseInt(s[0]);
            int E = Integer.parseInt(s[1]);
            A = new ArrayList[V + 1];
            visited = new boolean[V + 1];
            check = new int[V + 1];
            isEven = true;

            for (int i = 0; i <= V; i++) {
                A[i] = new ArrayList<Integer>();
            }

            for (int i = 0; i < E; i++) {
                s = br.readLine().split(" ");
                int Start = Integer.parseInt(s[0]);
                int End = Integer.parseInt(s[1]);
                A[Start].add(End);
                A[End].add(Start);
            }
            
            
            // Operating DFS
            for (int i = 1; i <= V; i++) {
                if (isEven)
                    DFS(i);
                else 
                    break;
            }
            check[1] = 0;
            
            
            // Output Extracting Cable
            if (isEven)
                System.out.println("YES");
            else
                System.out.println("No");
        }
    }
    
    // External Module DFS
    public static void DFS(int node) {
        visited[node] = true;
        for (int i : A[node]) {
            if (!visited[i]) {
                check[i] = (check[node] + 1)%2;
                DFS(i);
            } else if (check[node] == check[i]) {
                    isEven = false;
            }
        }
    }
}