BOJ 1707 이분 그래프

1 개요

BOJ 1707 이분 그래프

• 백준 온라인 저지 1707번 문제
• BOJ 31단계

2 C++

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

int K, V, E;
vector<vector<int>> A;
int visited[20001];

bool bfs(int s) {
    if(visited[s] != 0) {
        return true;
    }
    queue<int> q;
    q.push(s);
    visited[s] = 1;
    int x;
    while(!q.empty()) {
        x = q.front();
        q.pop();
        for(auto& nx: A[x]) {
            if(visited[nx] != 0) {
                if(visited[nx] == visited[x]) return false;
                continue;   
            }
            q.push(nx);
            visited[nx] = (visited[x] == 1) ? 2 : 1;
        }
    }
    return true;
}

bool solve() {
    for(int i=1; i<=V; i++) {
        visited[i] = 0;
    }
    for(int i=1; i<=V; i++) {
        if(!bfs(i)) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> K;
    while(K--) {
        cin >> V >> E;
        int u, v;
        A = vector<vector<int>>(V+1);
        for(int i=1; i<=E; i++) {
            cin >> u >> v;
            A[u].push_back(v);
            A[v].push_back(u);
        }
        cout << (solve() ? "YES" : "NO") << '\n';
    }
}