백준 : 1707

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

1707번: 이분 그래프

 

이분그래프

이분그래프란 인접한 노드들을 서로 다른색으로 2가지경우로만 칠할수있는 그래프이다.

문제를 풀기위해서 BFS를 이용해서 현재노드들을 색칠하고 인접노드를 탐색하는 것을 구현하면된다.

 

또한 끊어지 노드들에 대한 이분그래프가 있을수도 잇으므로 for을 통해 탐색한다.

 

package com.ssay.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B1707_2 {
    static int K;
    static int V, E;
    static int color[];
    static ArrayList<Integer> list[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        K = Integer.parseInt(br.readLine());
 
        for (int k = 0; k < K; k++) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
 
            list = new ArrayList[V + 1];
            for (int v = 1; v <= V; v++) {
                list[v] = new ArrayList<Integer>();
            }
 
 
            for (int e = 1; e <= E; e++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                list[u].add(v);
                list[v].add(u);
            }
 
            String Answer = "YES";
            color = new int[V + 1];
            boolean isPossible = false;
            for(int v=1;v<=V;v++) {
                if(color[v]!=0)continue;
                color[v] = 1;
                
                Queue<Integer> q = new LinkedList<Integer>();
                q.add(v);
                
                while(!q.isEmpty()) {
                    int now = q.poll();
                    int c = color[now];
                    
                    int size = list[now].size();
                    
                    for(int s=0;s<size;s++) {
                        int tmp = list[now].get(s);
                        if(color[tmp]==c) {
                            //이분그래프안됨
                            Answer = "NO";
                            isPossible = true;
                            break;
                        }
                        
                        if(color[tmp] == 0) {
                            color[tmp] = c*-1;
                            q.add(tmp);
                        }
                        
                    }
                    
                    if(isPossible)break;
                    
                }
                
            }
 
            System.out.println(Answer);
        }
    }
 
}