문제 출처

1. 문제설명


2. 알고리즘 설계

  • 이분 그래프는 well-known 알고리즘이다.
  • 정점을 어떤 색으로 칠한다.
    • 본인 코드에서는 칠해져 있지 않은 경우 0, 그렇지 않은 경우 -1 또는 1이다.
  • 프로세스
    • 처음 시작점(인접 행렬에서는 1번째)을 1로 칠한다.
    • 연결된 정점의 색을 칠한다.
      • 만약 이미 색이 칠해져 있는데, 시작점과 연결된 점이 같은 색이면 절대 이분 그래프가 될 수 없다.
      • 큐에 삽입한다.
    • 큐에서 꺼낸 정점은 (현재 색 * -1)을 취해 칠하는데, 위와 똑같은 검사를 진행한다.
    • 마지막 까지 될 수 없는 조건에 걸리지 않는다면 이분 그래프이다.


3. 전체 코드

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

const int SZ = 20005;
int K, V, E, u, v;
vector<int> adj[SZ];
vector<int> color;

bool bfs() {
    color.assign(V+5, 0);

    for(int i=1; i<=V; i++) {
        if(color[i] != 0) continue;

        queue<int> q;
        q.push(i);
        color[i] = 1;

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

            for(int nxt : adj[cur]) {
                if(color[nxt] != 0) {
                    if(color[nxt] == color[cur]) return false;
                    else continue;
                }
                color[nxt] = color[cur] * -1;
                q.push(nxt);
            }
        }
    }

    return true;
}

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

    cin >> K;
    while(K--) {
        cin >> V >> E;
        for(int i=1; i<=V; i++)
            adj[i].clear();

        while(E--) {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

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

    return 0;
}