[백준] 1707번 이분 그래프

문제: 1707번: 이분 그래프

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

using namespace std;

vector<vector<int>> graph;
vector<int> colors;

bool BFS(int start) {
    queue<int> nexts;
    nexts.push(start);
    // 일단 시작지점을 1으로 색칠해
    colors[start] = 1;

    while (!nexts.empty()) {
        int cur = nexts.front();
        nexts.pop();

        // 야 나랑 붙어있는 애들 돌면서 색칠해줘
        // 근데 나랑 붙어있는 애가 나랑 똑같은 색으로 색칠되어있다? ㄷㄷ No 출력해야함
        for (int next : graph[cur]) {
            if (colors[next] != 0) {
                // 이미 색칠되어 있는 경우
                // 만약 나랑 색이 똑같아? false 리턴
                if (colors[next] == colors[cur]) {
                    return false;
                }
            }
            else {
                // 색칠 안 되어 있는 경우
                nexts.push(next);
                colors[next] = (colors[cur] == 1 ? 2 : 1);
            }
        }
    }
    // 여기까지 도달했으면 true 리턴
    return true;
}

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

    int k;
    cin >> k;
    while (k-- > 0) {
        int v, e;
        cin >> v >> e;

        // 0번 인덱스 안 써
        graph = vector<vector<int>>(v + 1);
        colors = vector<int>(v + 1);
        for (int i = 0; i < e; i++) {
            int u, v;
            cin >> u >> v;

            // 방향이 없는 그래프
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        bool flag = true;
        for (int i = 1; i <= v; i++) {
            if (colors[i] != 0) continue;

            if (!BFS(i)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }

    return 0;
}

 

음 저번에 풀었던 색칠하기 문제랑 똑같은 문제인 것 같다. 

 

그냥 서로 접해있는 정점끼리는 색이 같으면 안 된다는 게 문제 핵심임을 파악하면 m-coloring 을 BFS 로 구현해서 쉽게 해결할 수 있다.

 

현재 정점이랑 연결되어 있는 노드를 색칠하려고 봤을 때 이미 색칠되어 있다면 현재 정점의 색이랑 비교해줘야 한다. 만약 현재 정점이랑 색이 같다? 이건 불가능한 경우니까 바로 false 리턴해주도록 했다.

 

만약 색칠되어 있지 않다면 그냥 현재 노드랑 다른 색으로 색칠하고 nexts 에 정점 번호를 넣어주면 된다.

 

nexts 가 빌때까지 무사히 돌면 마지막에 true 를 반환하도록 했다.