이분 그래프 1707

문제

접근 방법

이분 그래프가 뭔지 모르면 풀기 힘들 것이다.
쉽게 말해서 연결된 정점은 다른 그룹이어야 하는데 그것이 모든 정점에 대해서 만족해야 하는 것이다.
더 쉽게 말하자면 정점 A가 x라면 A랑 연결된 건 B, C, D는 y이어야 하고 B와 연결된 건 x이어야 하는 것이다.
더욱더 쉽게 말하면 정점을 탐색한다고 할 때 정점의 분류가 x, y, x, y, x, y 이런 식으로 나와야 한다는 것이다.

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int vState[20001], K, V, E;
vector<int> edge[20001];
bool bfs()
{
    queue<int> q;
    for (int i = 1; i <= V; ++i)
    {
        if (vState[i])
            continue;
        q.push(i);
        vState[i] = 1;
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (int j : edge[cur])
            {
                if (vState[j])
                {
                    if (vState[j] == vState[cur])
                    {
                        return false;
                    }
                    continue;
                }
                if (vState[cur] == 1)
                {
                    vState[j] = 2;
                }
                else
                {
                    vState[j] = 1;
                }
                q.push(j);
            }
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> K;
    while (K--)
    {
        cin >> V >> E;
        for (int i = 1; i <= V; ++i)
        {
            edge[i].clear();
            vState[i] = 0;
        }
        while (E--)
        {
            int n1, n2;
            cin >> n1 >> n2;
            edge[n1].push_back(n2);
            edge[n2].push_back(n1);
        }
        cout << (bfs() ? "YES" : "NO") << "\n";
    }
}

풀이

아직 탐색하지 않으면 상대편 그룹으로 표시하고 탐색했다면 다른 거면 넘어가고 같은 거면 false를 반환한다.
내가 틀렸던 부분은 모든 정점이 연결되지 않았다는 점을 고려하지 못해 틀렸다. 즉 그래프가 2개 이상일 수 있다는 것이다.
반복문을 통해 모든 정점에서 탐색하게 하면 해결된다.