[백준] 1707. 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

---

문제를 풀기 위해서 이분 그래프의 개념을 확실하게 알고가야 합니다.

https://terms.naver.com/entry.nhn?docId=855702&cid=50371&categoryId=50371

그래프를 두 그룹으로 나누어서 각 그룹이 서로 연결되어 있지 않다면 이분 그래프라고 합니다. 그래서 처음 1번 정점에 시작해서 DFS를 하는데 처음 시작하는 정점을 1로 시작했다면 1과 연결되어 있는 점은 2번으로 표시합니다. 그리고 2번이라고 표시되어 있는 점과 연결되어있는 점들을 1로 표시하여 그래프를 두 그룹으로 나누었습니다.

그럼 최종적으로 표시되는 그래프의 정점들에 저장된 번호들은 1 아니면 2가 저장되어있고, 연결되어있는 점들의 번호를 확인해서 같은 번호가 저장되어있으면 이분그래프가 아닌것으로 판단합니다.

[문제 풀이]

1. ArrayList 배열에 정점과 연결되어 있는 정점들을 저장합니다.

2. visited 배열에는 0, 1, 2가 저장 됩니다.  0 -> 방문하지 않음 / 1 -> 그룹 A / 2 -> 그룹 B

3. 1번 정점부터 DFS(정점 번호, 그룹을 나타내는 숫자) 를 시작합니다. 1번은 임의로 A그룹이라고 시작합니다.

3-1. DFS 의 3-type 부분은 다음 정점은 1, 2를 번갈아가면서 표시하기 위해서 입니다.

4. DFS가 끝나면 visited에 1, 2가 저장되어 있고, 각 정점에서 연결된 정점들에 번호가 같은지 검사합니다.

---

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

public class Main {
	
	static int K, V, E;
	static ArrayList<Integer>[] list;
	static int[] visited;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		K = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=K; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			visited = new int[V+1]; // 0:방문x, 1:groupA, 2:groupB
			list = new ArrayList[V+1];
			for(int i=1; i<=V; i++) list[i] = new ArrayList();
	
			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				list[a].add(b);
				list[b].add(a);
			}
			
			for(int i=1; i<=V; i++) {
				if(visited[i] == 0) {
					dfs(i, 1);
				}
			}
			
			boolean flag = true;
			
			Out : for(int i=1; i<=V; i++) {
				for(int j : list[i]) {
					if(visited[j] == visited[i]) {
						flag = false;
						break Out;
					}
				}
			}
			
			if(flag) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}

	public static void dfs(int x, int type) {
		visited[x] = type;
		for(int i=0; i<list[x].size(); i++) {
			int nx = list[x].get(i);
			if(visited[nx] == 0) {
				dfs(nx, 3-type);
			}
		}
		
	}
}