[백준(Baekjoon)][자바(java)] 1707 : 이분 그래프 / DFS와 BFS

 

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int t = Integer.parseInt( br.readLine() ), nv, ne, a, b, i, k, ci, cj, cn;  
		// test case, num_vertexs, num_edges, color_i, color_j, color_next
		List<List<Integer>> e;	// edge
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		Deque<Integer> q;		// queue
		int c[];				// color ( 0 : not visited, 1 : red, -1 : blue )
		boolean bipartite;		// is bipartite graph ?
		while( t-- > 0 ) {
			st = new StringTokenizer( br.readLine() );
			nv = Integer.parseInt( st.nextToken() );
			ne = Integer.parseInt( st.nextToken() );
			e = new ArrayList<>();
			for( i = 0; i < nv; i++ )
				e.add( new ArrayList<>() );
			for( i = 0; i < ne; i++ ) {
				st = new StringTokenizer( br.readLine() );
				a = Integer.parseInt( st.nextToken() ) - 1;
				b = Integer.parseInt( st.nextToken() ) - 1;
				if( a == b ) continue;
				e.get( a ).add( b );
				e.get( b ).add( a );
			}
			q = new LinkedList<>();
			c = new int[nv];
			bipartite = true;
			loop:
			for( k = 0; k < nv; k++ ) {
				if( c[k] == 0 ) {  // not visited
					q.addLast( k );
					c[k] = 1;  // red
					while( !q.isEmpty() ) {
						i = q.pollFirst();
						ci = c[i];
						cn = ci * (-1);  // red <-> blue
						for( int j : e.get( i ) ) {
							cj = c[j];
							if( cj == 0 ) {  // not visited
								q.addLast( j );
								c[j] = cn;
							}
							if( cj == ci ) {  // adjacent but same color -> not bipartite graph
								bipartite = false;
								break loop;
							}
						}
					}
				}
			}
			sb.append( ( bipartite ? "YES" : "NO" ) + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
	}
}

 

*  BFS

-  그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부름
-  이분 그래프는 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프
-  각 정점의 색깔 정보를 저장할 int c[] 배열 생성 ( 0 = 아직 방문 안함, 1 = 빨간색, -1 = 파란색 )
-  방문하지 않은 정점들에 대해 BFS를 하며 그 정점은 빨간색으로 칠하고, 그와 인접한 정점은 파란색으로 칠한다.
   만약 인접한 정점이 이미 현재 정점과 같은 색으로 칠해져 있다면 이분 그래프가 아니다

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84#%EB%B3%80%EB%B3%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

< 이분 그래프 >

성질
-  홀수 길이의 순환이 존재하지 않는다.

변별 알고리즘
-  주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 그래프의 꼭짓점들을 깊이 우선 탐색으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 이 알고리즘은 O(|V|+|E|)이다.