1707

이분 그래프 : https://www.acmicpc.net/problem/1707

 

https://toastfactory.tistory.com/115

https://kukekyakya.tistory.com/96

 

 

DFS 및 BFS풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {

	static int V, E, T;
	static boolean DBG = false;
	static String answer = "YES";
	static ArrayList<ArrayList<Integer>> graph;
	static int[] visited, team;
	static int RED = -1;
	static int GREEN = 1;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			answer = "YES";
			found = false;
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			visited = new int[V];
			team = new int[V];
			graph = new ArrayList<ArrayList<Integer>>();

			for (int i = 0; i < V; i++) {
				graph.add(new ArrayList<Integer>());
			}

			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken()) - 1;
				int v2 = Integer.parseInt(st.nextToken()) - 1;
				graph.get(v1).add(v2);
				graph.get(v2).add(v1);
			}

			if (DBG) {
				int i = 0;
				for (ArrayList<Integer> arr : graph) {
					System.out.print("i : [" + i + "] ");
					i++;
					for (int v : arr) {
						System.out.print(v + " ");
					}
					System.out.println();
				}

			}

			for (int i = 0; i < V; i++) {
				if (visited[i] == 0) {
					dfs(0, i, 1);
					if (found)
						break;
				}
			}

			/*
			 * for (int i = 0; i < V; i++) if (team[i] == 0) { if (!bfs(i)) break; }
			 */

			System.out.println(answer);
		}

	}

	static boolean found = false;

	private static void dfs(int level, int vex, int color) {

		if (visited[vex] != 0)
			return;
		visited[vex]=1;
		team[vex] = color;

		for (int v : graph.get(vex)) {
			if (team[v] == team[vex]) {
				answer ="NO";
				found =true;
				return;
			}
			dfs(level + 1, v, color * -1);
		}

	}

	private static boolean bfs(int vex) {
		Queue<Integer> Q = new LinkedList<>();

		Q.offer(vex);
		team[vex] = RED;

		while (!Q.isEmpty()) {
			int now = Q.poll();
			for (int n : graph.get(now)) {
				if (team[now] == team[n]) {
					answer = "NO";
					return false;
				}
				if (team[n] == 0) {
					team[n] = team[now] * -1;
					Q.add(n);
				}

			}
		}
		return true;
	}

}