[BOJ / C++] 이분 그래프 (그래프)

문제링크: https://www.acmicpc.net/problem/1707

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int tc;
    cin >> tc;

    while (tc--) {
        int v, e;
        cin >> v >> e;
        
        vector<vector<int>> adj(v+1);
        for (int i = 0; i < e; i++) {
            int a, b;
            cin >> a >> b;

            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        
        vector<int> group(v+1, 0); // 0: unvisited, 1/-1: group
        bool ok = true;

        for (int st = 1; st <= v; st++) {
            if (!ok) break;
            if (group[st] != 0) continue;
            
            queue<int> Q;
            group[st] = 1;
            Q.push(st);

            while (!Q.empty()) {
                int cur = Q.front(); Q.pop();
                for (int nxt : adj[cur]) {
                    if (group[nxt] != 0 && group[nxt] == group[cur]) {
                        ok = false;
                        break;
                    }
                    else if (group[nxt] == 0) {
                        Q.push(nxt);
                        group[nxt] = -group[cur];
                    }
                }
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

 

 

2. 시간복잡도

인접리스트에서 BFS 순회는 O(v+e)이다. v = 20,000, e = 200,000 이므로 220,000 < 10^8이고 따라서 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

 

이 부분 해석이 중요하다. 각 집합에 속한 정점끼리 인접하지 않아야한다는 것은 두 그룹으로 나눴을 때 같은 그룹 안에서는 간선이 없어야한다는 뜻이다. 

 

이 부분을 색칠 문제로 치환해서 생각하면 쉽게 이해할 수 있다. 그래프를 BFS로 순회하며 나는 1로 색칠하면 간선으로 연결된 다음 정점은 -1로 색칠해야하는 것이다. 그래야 둘은 다른 그룹이 된다. 그래서 순회를 하면서 이미 방문을 했고 && group[nxt] == group[cur]이라면 NO가 된다.

 

그리고 이 작업은 모든 정점을 시작점 후보로 해줘야한다. 즉, st = 1 .. n까지 수행해줘야한다. 왜냐하면 그래프가 모든 정점이 연결되어있지 않고 비연결 그래프일 수 있기 때문이다.

 

(예시 사례)

정점 1—2 (단순 간선)

정점 4—5—3—4 (홀수 사이클)

길이가 홀수인 싸이클을 홀수 싸이클이라고 하고, 길이가 짝수인 싸이클을 짝수 싸이클이라고 한다.

 

• 그래프에 홀수 사이클이 하나라도 있으면 → 이분 그래프 불가.
• 사이클이 모두 짝수이거나, 아예 사이클이 없으면 → 이분 그래프 가능.

이분그래프에서는 이런 관계를 갖는다.