백준 1707번: 이분 그래프 (C++)

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

가령 1--2--3--4 

이러한 연결 관계를 가지는 그래프가 주어지면, 1을 빨간색, 2를 초록색으로 칠하고, 다시 3을 빨간색 4를 초록색

이렇게 두 가지의 색을 이용하여, 그래프의 모든 노드를 인접한 노드의 삭과 다른 색으로 색칠 할 수 있는지

검증하는 문제이다.

색깔의 구현은, 방문 처리 배열의 값을 1과 2사이에서 토글되게 하였다. 0이면 방문하지 않은것

#pragma warning(disable :4996)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
vector<int> grp[20001];
 
int vis[20001]; //초기 0, 두종류 1,2 -> 인접한 정점간에 다른 vis 값을 가지면 이분그래프
int vCnt, eCnt;
bool isBigrp = true;
queue<int> q;
void bfs(int st) {
    q.push(st);
    vis[st] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < grp[cur].size(); i++) {
            
            int next = grp[cur][i]; //확인할 지점
            
            if (vis[next] != 0 && vis[cur] == vis[next]) { //인접한 정점과 같은 vis값을 가지는 경우
                cout << "NO\n";
                isBigrp = false;
                return;
            }
            if (vis[next] > 0) continue; //재방문 못하게
            q.push(next);
            vis[next] = vis[cur] % 2 + 1; //cur이 1이면 next는 2가되고, vice versa
            
        }
    }
    
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> vCnt >> eCnt;
        for (int i = 0; i < eCnt; i++) {
            int src, dst;
            cin >> src >> dst;
            grp[src].push_back(dst);
            grp[dst].push_back(src);
        }
        
        for (int i = 1; i <= vCnt; i++) {
            if (vis[i] == 0) {
                bfs(i);
                if (!isBigrp) break; // 이분그래프가 아니라는 결론이 났으면 더 진행할 필요가 없다
            }
        }
        if(isBigrp)
            cout << "YES\n";
 
        //이 아래로는 초기화 부분
        while (!q.empty()) q.pop();
        for (int i = 1; i <= vCnt; i++) {
            vis[i] = 0;
            grp[i].clear();
        }
        isBigrp = true;
    }
    return 0;
}