자바로 백준 1707 풀기

풀이)
이분 그래프란 1-2-3 node가 연결되어있을 때, {1,3}과 {2} 집합으로 나뉠 수 있는 그래프이다.
즉, 그래프를 탐색하는데 시작 노드를 A 집합에 넣으면 주변 노드를 B 집합에, 시작 노드가 B 집합이라면 주변노드를 A 집합에 넣고, 만약 노드가 이미 집합 내에 들어가있는데 잘못된 위치에 들어가있다면 이분 그래프가 아니라고 출력하면 된다.
이를 위해선 너비우선탐색인 BFS를 진행하면 된다.

최악의 경우 테스트 케이스는 5개이므로 인접리스트를 통해 그래프를 입력받는다.

코드)

// 백준 온라인 저지 1707번
import java.io.*;
import java.util.*;

public class Main{
	
	static ArrayList<Integer>A[];
	static int check[];
	static boolean visited[];
	static boolean IsEven;
	
	static void DFS(int start) {
		visited[start] = true;
		for(int i : A[start]) {
			//start 옆 인접 노드들 탐색하기
			if(!visited[i]) {
				check[i] = (check[start] + 1) % 2;
				DFS(i);
			}else {
				if(check[i] == check[start]) {
					IsEven = false;
				}
			}
		}
	}
	
	public static void main(String[]args) throws IOException{		
		
		// 입력.
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		
		for(int t=0;t<T;t++) {
			// 인접리스트로 그래프 입력.
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			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++) {
				st = new StringTokenizer(bf.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				A[s].add(e);
				A[e].add(s);
			}
			
			// 탐색.
			for(int j=1;j<=V;j++) {
				if(IsEven) {
					DFS(j);
				}else {
					break;
				}
			}			
			if(IsEven) {
				System.out.println("YES");
			}else
				System.out.println("NO");
		}			
	}
}