Bipartite Graph

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

1707번: 이분 그래프

 

 

문제 설명에 나와있듯이, 이분 그래프란 "그래프의 정점을 두 개의 집합으로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는" 그래프입니다. 이를 만족하기 위해서 그래프의 인접한 두 정점은 서로 다른 집합에 속해야 합니다.

 

 

 

 

예를 들어, 왼쪽과 같은 그래프가 있습니다. 각 노드는 빨간/파란색인데, 이 색은 집합을 나타냅니다. 왼쪽의 그래프는 사실 오른쪽 그래프로 변환 가능합니다. 오른쪽의 그래프를 보면, 파란색 노드들끼리는 서로 인접하지 않으며, 빨간색 노드들끼리도 서로 인접하지 않은 것을 볼 수 있습니다. 즉, 위의 그래프는 이분 그래프입니다.

 

어떤 그래프가 이분 그래프인지 아닌지의 판단은 그래프 탐색 알고리즘을 통해 가능합니다. 대표적인 그래프 탐색으로는 bfs, dfs가 있습니다. 둘 중 어느 것을 사용해도 판단이 가능하지만, 저는 bfs를 이용하여 문제를 해결하였습니다.

 

 

 

 

위와 같은 원래의 그래프에서, $1$번 노드부터 bfs를 시작합니다. 탐색 도중 어떤 노드의 인접한 노드들을 방문할 때마다, 그 노드를 빨강 혹은 파랑으로 색칠할 것입니다. 이 때, 인접한 노드의 색은 자신의 색과 다른 색으로 칠합니다. 이 때, 자신과 인접한 노드가 이미 자신과 같은 색으로 칠해져 있다면, 그 그래프는 이분 그래프가 아닙니다. 반대로, 그런 일이 없이 모든 노드를 색칠할 수 있으면 그 그래프는 이분 그래프입니다. 

 

$1$번 노드를 우선 파란색으로 칠하고 bfs를 시작합니다.

 

 

 

 

 

 

 

 

 

bfs통해 모든 노드를 방문하고 색칠했습니다. 그런데 우리는 위의 그래프가 이미 이분 그래프임을 압니다. 그래서 탐색이 성공적으로 끝난 것은 당연합니다. 이번에는 이분 그래프가 아닌 그래프에서의 bfs를 봅시다.

 

 

 

 

위의 그래프는 이분 그래프가 아닙니다. 원래 이분 그래프에서 같은 집합이었던 노드$5, 6$을 인접하게 만들었기 때문입니다. 이 그래프 위에서의 bfs는 아래와 같습니다.

 

 

 

 

 

$1$번 노드에 인접한 노드인 $5, 6$번 노드를 방문했습니다. 그 후에는 $5$번 노드의 인접한 노드를 방문할 차례입니다. 그런데 $5$번 노드의 인접한 노드인 $6$번 노드가 이미 $5$번 노드와 같은 색으로 칠해져 있습니다. 이러한 경우가 생길 경우, 해당 그래프는 이분 그래프가 아니라고 했습니다. 더 이상 탐색할 필요 없이 종료하면 됩니다.

 

 

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define BLUE 1
#define RED 2
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
using namespace std;
int vis[20001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int K;
    cin >> K;

	for(int k=0; k<K; k++){
        memset(vis, 0, sizeof(vis));
        vector<int> adj[20001];
        int V, E;
        cin >> V >> E;

        // 그래프 정보 입력받기.
        for (int e = 0; e < E; e++) {
            int n1, n2;
            cin >> n1 >> n2;
            adj[n1].push_back(n2);
            adj[n2].push_back(n1);
        }

        queue<int> q;
        bool ok = 1;
        for(int v=1; v<=V; v++){
            if(!vis[v]){
                vis[v] = BLUE;
                q.push(v);
                while(!q.empty() && ok){
                    int cur = q.front();
                    int color = vis[cur];
                    q.pop();
                    for(int a=0; a<sz(adj[cur]); a++){
                    int next = adj[cur][a];
                    // 이분 그래프가 아닐 경우 이 구문에 걸린다.
                    if(vis[next] == color){
                        ok = 0;
                        break;
                    // 인접한 노드를 자신과 다른 색으로 칠한다.
                    }else if(!vis[next]){
                        vis[next] = (color == BLUE ? RED : BLUE);
                        q.push(next);
                    }
                }
            }
        }
    }
    cout << (ok ? "YES\n" : "NO\n");
    }
}