백준_이분 그래프

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

[ 그림1. 이분 그래프 설명 ]

[ 나의 해결법 ]

그림1처럼 각 집합(파랑색과 빨강색)안에 노드들끼리 간선이 없으면 이분그래프가 된다.

그럼 어떻게 이분그래프인지 알 수 있을까?

주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다. [ 출처 : 위키백과 ]

이 문제에서 주의해야할 점은 다른 노드들과는 아예 분리된 노드가 존재할 수 있다는 것이다. 그림1과 같은 그래프 두 개가 간선이 끊어진 채로 존재할 수 있다.

이분 그래프 확인을 위해서 그래프 탐색을 해야한다. 너비우선탐색(BFS)과 깊이우선탐색(DFS)로 문제를 해결할 수 있다. 나는 너비우선탐색(BFS)를 이용했다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

#include <iostream> #include <vector> #include <queue>   #define MAXNODE 20001 #define RED     1   using namespace std;   int K, V, E; vector<int> Graph[MAXNODE]; vector<int> color(MAXNODE, 0);   bool BFS(int start) {     queue<int> q;       q.push(start);     color[start] = RED;       while (!q.empty())     {         int cur = q.front();         q.pop();           for (int i = 0; i < Graph[cur].size(); i++)         {             int next = Graph[cur][i];               if (color[next] == 0)             {                 color[next] = ~color[cur];                 q.push(next);             }             else             {                 if (color[next] == color[cur])                     return false;             }         }     }       return true; }   int main() {     cin >> K;       while (K--)     {         int src, dst;         bool res = true;           cin >> V >> E;           for (int i = 1; i <= V; i++)             Graph[i].clear();         color.assign(V + 1, 0);           for (int i = 0; i < E; i++)         {             cin >> src >> dst;             Graph[src].push_back(dst);             Graph[dst].push_back(src);         }           for (int i = 1; i <= V; i++)         {             if (color[i] == 0)                 res &= BFS(i);         }           if (res == true)             cout << "YES" << endl;         else             cout << "NO" << endl;     }     return 0; }