BOJ 1707:: 이분 그래프

변으로 이어진 꼭짓점끼리 다른 색으로 칠해서 모든 꼭짓점을 두 색으로만 칠할 수 있는지 판정하면 됩니다. 이분 그래프는 BFS를 할 때 같은 레벨의 꼭짓점끼리는 항상 같은 색으로 칠해집니다. 그래서 어떤 꼭짓점에서 시작해 BFS로 꼭짓점을 방문하다가 만약 한 레벨 안에서 꼭짓점을 다른 색으로 칠해야 하는 일이 있으면 반드시 이분 그래프가 아닌 것이고, 모든 꼭짓점을 다 방문했는데도 그런 일이 없으면 이분 그래프인 것이죠. 단, 그래프가 연결 그래프가 아니면 BFS로 모든 꼭짓점을 방문할 수 없으므로 일단 한 꼭짓점과 그와 연결된 꼭짓점을 방문한 후 남은 꼭짓점이 있으면 계속 BFS를 돌립니다. 연결 요소 계산하는 방식이랑 똑같이 말이죠.

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

using namespace std;

bool isBipartite(vector<vector<int>> &Adj) {
    int v = Adj.size();
    int Color[v] = {0};

    queue<int> Q;

    for (int i=0; i<v; i++) {
        if (Color[i] != 0) continue;

        Q.push(i);

        while (!Q.empty()) {
            int Qsize = Q.size();
            for (int j=0; j<Qsize; j++) {
                int current = Q.front();
                Q.pop();

                int adjColor = 0;
                for (int next: Adj[current]) {
                    if (Color[next] == 0) Q.push(next);
                    else {
                        if (adjColor == 0) adjColor = Color[next];
                        else if (adjColor != Color[next]) return false;
                    }
                }

                Color[current] = (adjColor==0)?1:(3-adjColor);
            }
        }
    }

    return true;
}

int main(void) {
    int k;
    cin >> k;

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

        vector<vector<int>> Adj(v);

        for (int i=0; i<e; i++) {
            int start, end;
            scanf("%d %d", &start, &end);
            Adj[start-1].push_back(end-1);
            Adj[end-1].push_back(start-1);
        }

        if (isBipartite(Adj)) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}