[백준OJ] 1707번 이분 그래프

 

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

1707번: 이분 그래프

---

풀이

BFS를 이용해서 모든 노드에 색을 칠해주었습니다. 해당 색을 Boolean의 TRUE, FALSE를 이용하여 색을 부여하였고, BFS를 돌며 탐색되지 않은 노드에 대해서는 현재 노드의 색과 반대되는 색을 칠해주고 Queue에 넣기, 탐색이 된 노드는 현재 노드와 색을 비교하여 이분 그래프가 되는지에 대해 판별하도록 했습니다.

 

주의할 점은 그래프가 모두 이어져있는것이 아니라, 여러 그룹의 그래프가 나올 수 있으니, 이를 고려하여 문제를 해결합니다.

시간복잡도

일반적인 BFS이므로 O(VE) 의 시간복잡도를 갖는다.

코드

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 Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.valueOf(br.readLine());

        while(t-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v = Integer.valueOf(st.nextToken());
            int e = Integer.valueOf(st.nextToken());

            boolean[] nodes = new boolean[v+1];
            boolean[] visited = new boolean[v+1];

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

            for(int i=0;i<e;i++){
                st = new StringTokenizer(br.readLine());

                int a = Integer.valueOf(st.nextToken());
                int b = Integer.valueOf(st.nextToken());

                graph.get(a).add(b);
                graph.get(b).add(a);
            }
            boolean can = true;
            for(int start = 1 ; start <=v ;start++) {
                if(visited[start]) continue;
                Queue<Integer> q = new LinkedList<>();
                q.offer(start);
                visited[start] = true;
                nodes[start] = true;

                while (!q.isEmpty()) {
                    int now = q.poll();

                    for (int next : graph.get(now)) {
                        if (!visited[next]) {
                            visited[next] = true;
                            nodes[next] = !nodes[now];
                            q.offer(next);
                        } else {
                            if (!(nodes[now] ^ nodes[next])) {
                                can = false;
                            }
                        }
                    }
                }
            }

            System.out.println(can ? "YES" : "NO");

        }
    }
}