백준 1707번 - 이분 그래프

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

1707번: 이분 그래프

 

이분 그래프의 설명을 이해하기 어려워서 위키백과를 참고했습니다

 

• 문제 해결 방법

노드를 탐색할때 1과 0이 번갈아 나타나도록 방문처리를 해주면서 탐색도중 같은 방문값이 연속적으로 나타난다면 NO를 출력하고 그렇지 않으면 YES를 출력하도록 했습니다.

 

입력되는 데이터 중 연결되지 않은 집합이 존재할 수 있으므로 모든 노드의 방문을 확인해 주어야 합니다.

 

 

 

 

• C++ 전체 코드

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

int T,N,K;
vector<int> adj[20001]{};
int vi[20001]{};

bool bfs(int st){
    queue<int> q;
    q.push(st);
    vi[st] = 0;
    while(!q.empty()){
        int now = q.front();
        q.pop();

        for(auto next : adj[now]){
            if(vi[next] == vi[now]) return false;
            if(vi[next] == -1) {
                vi[next] = !vi[now];
                q.push(next);
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b;
    cin>>T;
    while(T--){
        cin>>N>>K;
        memset(vi,-1,sizeof(vi));
        for(int i=0; i<=N; i++) adj[i].clear();
        for(int i=0; i<K; i++){
            cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        bool chk = true;
        for(int i=1; i<=N; i++) {
            if(vi[i] != -1) continue;
            if(!bfs(i)) {
                chk = false;
                break;
            }
        }
        if(chk) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}