1707_이분 그래프 (JAVA)

1707번: 이분 그래프

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

public class Main {
	static int n;
	static int m;
	static ArrayList<Integer>[] graph;
	static int[] color;
	static boolean flag = false;

    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testcase = Integer.parseInt(br.readLine());
		for(int i=0; i<testcase; i++){
			flag = false;
            
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			color = new int[n+1];
			graph = new ArrayList[n+1];
			for(int k=1; k<=n; k++){
				graph[k] = new ArrayList<>();
			}

			for(int j=0; j<m; j++){
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());
				graph[v1].add(v2); graph[v2].add(v1);
			}

			for(int l=1; l<=n; l++){
				if(color[l] == 0){ //방문 안했을 때
					color[l] = 1;
					dfs(l,1);
				}
			}

			if(!flag) System.out.println("YES");
			else System.out.println("NO");
		}

		br.close();
    }

    private static void dfs(int v, int v_color){
    	if(flag) return;

    	color[v] = v_color;

		for(int i=0; i<graph[v].size(); i++){
			if(color[graph[v].get(i)] == v_color){ //연결된 점과 색이 같을 때
				flag = true;
				return;
			}
            
			if(color[graph[v].get(i)] == 0){ //방문 안했을 때
				dfs(graph[v].get(i), 3-v_color);
			}
		}
	}
}

 

0,1,2 세 가지의 수로 color[] 배열에 표시했다. 

0일 때는 방문안했을 때, 1일 때와 2일 때는 각각 두 가지 그룹을 의미한다.

 

DFS 재귀로 구현했다.연결된 정점의 색이 0일 때 -> dfs 재귀로 다시 돌리고,연결된 정점의 색이 1이나 2일 때에는

-> 기존 정점의 색과 비교하여 같은 경우 : 이분그래프 아니므로 탐색 종료,                                                      

                                                      다른 경우 : 생각하지 않았다.

                                        (왜냐면, main에서 for문으로 모든 정점을 dfs에 넣기 때문에)

 

 

 

구현 내용을 단계별로 풀어 설명하면 다음과 같다.

 

1. dfs()함수를 통해 한 정점에서 연결된 점들을 파악한다.

   1) dfs(x)일 때, '정점x의 색'과 '정점x와 연결된 정점의 색'이 같다면 - 모순이 발생한다.

      flag=true로 변경하고 모든 dfs탐색을 중단한다.

 

   2) 정점x와 연결된 정점이 처음 방문하는 거라면 (== color[]=0일 때)

      정점x의 색과 다른 색으로 설정하여 재귀로 돌린다.

      (정점x가 1의 색을 갖는다면 2로 설정, 2의 색을 갖는다면 1로 설정)

 

2. flag가 true인 경우 이분그래프가 아니고, false인 경우 이분그래프를 의미한다.