[백준/C++] 1707번: 이분 그래프

문제 & 링크

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

풀이

1. 이분 그래프란 그래프를 두 집합(A, B)으로 분할했을 때, 같은 집합에 속한 정점끼리는 간선이 없는 것이다. -> 쉽게 말하면 노드가 홀수 개인 사이클이 없는 것

    A -> B로의 간선 존재 가능, B -> A로의 간선 존재 가능, A -> A & B -> B로의 간선 존재 불가능

1. 각 노드에 색을 입혀, 짝수 번 노드와 홀수 번 노드를 구분한다. color 배열을 이용하여 -1이면 방문하지 않은 점, 0이면 짝수 노드, 1이면 홀수 노드로 표시한다.

2. K개의 테스트 케이스가 있기에 인접 리스트(그래프)와 color를 초기화한다.

3. 모든 노드에 대해서 BFS를 수행한다. 이때 아직 방문하지 않은 점(color = -1)에 대해서만 수행한다.

4. 현재 탐색 중인 노드와 앞으로 탐색할 노드의 색을 비교한다. 만약 두 노드의 색이 같으면 노드가 홀수 개인 사이클이 발생한 것으로 이분 그래프가 아니라는 것을 알 수 있다.

5. 5번의 조건에 걸리지 않을 경우 앞으로 탐색할 노드는 현재 노드와 다른 색으로 입히고, BFS 큐에 추가한다.

    현재 노드가 0이면 탐색할 노드는 1로, 현재 노드가 1이면 탐색할 노드는 0으로

1. 주어진 인접 리스트에 대해서 모든 정점에 대한 탐색이 끝나면 이분 그래프인지 아닌지 알 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int color[20001];
vector<int> adj[20001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int K;

    cin >> K;

    int V, E;
    while (K--) {
        cin >> V >> E;

        fill(color, color + V + 1, -1);
        for (int i = 1; i <= V; i++) adj[i].clear();
   
        int s, e;
        for (int i = 0; i < E; i++) {
            cin >> s >> e;

            adj[s].push_back(e);
            adj[e].push_back(s);
        }

        bool passible = true;
        for (int i = 1; i <= V; i++) {
            queue<int> q;
            if (color[i] == -1) {
                q.push(i);
                color[i] = 0;
            }

            while (!q.empty()) {
                int node = q.front();
                q.pop();

                for (int j = 0; j < adj[node].size(); j++) {
                    if (color[node] == color[adj[node][j]]) {
                        passible = false;
                        break;
                    }

                    if (color[adj[node][j]] == -1) {
                        q.push(adj[node][j]);
                        if (color[node]) color[adj[node][j]] = 0;
                        else color[adj[node][j]] = 1;
                    }

                }
                if (!passible) break;
            }
            if (!passible) break;
        }
        if (!passible) cout << "NO" << "\n";
        else cout << "YES" << "\n";
    }
}