시간 제한 : 2초, 난이도 : 골드 4, 백준 : 1707번

• 이분 그래프 : 각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때 이 그래프를 ‘이분 그래프’라고 한다.
• 왜 BFS가 아니라 DFS를 사용할까? →
• “모든 노드”에 대해서 DFS를 실행 해야 한다. → 그래프가 모두 이어진 형태가 아닐 수도 있기 때문에

DFS

• 스택 또는 재귀 함수를 이용하여 구현할 수 있음
• 시작 노드에서부터 한 경로를 따라 최대한 깊게 탐색한 후, 다른 경로를 탐색함
• 그래프의 구조를 파악하는데 유용함
• 미로 찾기 등의 문제를 해결하는데 활용됨

BFS

• 큐를 이용하여 구현할 수 있음
• 시작 노드에서부터 인접한 노드를 모두 탐색한 후, 다음 노드로 이동함
• 최단 경로를 찾거나, 노드 간 최단 거리 등을 구하는데 활용됨

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

public class Practice48 {
	static ArrayList<Integer>[]A;
	static int[] check;
	static boolean visited[];
	static boolean IsEven;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		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 = 1; 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);
			}
			
			for(int i = 1; i <= V; i++) {
				if(IsEven)
					DFS(i);
				else
					break;
			}
			if(IsEven)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
	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;
			}
		}
	}
}