📍 1. 문제

📍 2. 풀이

1. 그래프 생성
2. 분할된 그래프인지 고려하여 방문하지 않은 모든 노드를
   그래프 탐색하면서 색(color) 설정
3. 연결리스트 순회
   ex) 1번과 연결된 노드(list[1]과 연결된 노드)는 1번노드와 색이 반대여야한다.
4. 3번 여부에 따라 YES NO 출력.

📍 3. 코드

인접리스트 + DFS-Recursive

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int testcount = Integer.parseInt(st.nextToken());
		for(int x = 0; x < testcount; x++) {
			
			st = new StringTokenizer(br.readLine());
			int vertex = Integer.parseInt(st.nextToken());
			int edge = Integer.parseInt(st.nextToken());
			
			boolean[] visited = new boolean[vertex + 1];
			boolean[] colors = new boolean[vertex + 1];
			ArrayList<Integer>[] list = new ArrayList[vertex + 1];
			for(int i = 0; i < list.length; i++) {
				list[i] = new ArrayList<Integer>();
			}
			
			for(int i = 0; i < edge; i++) {
				st = new StringTokenizer(br.readLine());
				
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());
				
				list[v1].add(v2);
				list[v2].add(v1);
			}
				
			for(int i = 1; i < list.length; i++) {
				if(visited[i] == false) {
					dfsRecursive(i, list, visited, colors, true);					
				}
			}
			
			boolean answer = true;
			for(int i = 1; i < list.length; i++) {
				if(answer == false) break;				
				for(int e : list[i]) {
					if(colors[i] == colors[e]) {
						answer = false;
						break;
					}
				}
			}
			if(answer == false) {
				System.out.println("NO");
			}else {
				System.out.println("YES");				
			}
			
		}
	}
	
	public static void dfsRecursive(int vertex, ArrayList<Integer>[] list, boolean[] visited, boolean[] colors, boolean color) {
		visited[vertex] = true;
		colors[vertex] = color;
		
		for(int e : list[vertex]) {
			if(visited[e] == false) {
				dfsRecursive(e, list, visited, colors, !color);
			}
		}
	}
}