백준 1707:이분 그래프

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

백준 1707번 이분 그래프 문제입니다.

이번에는 C++로 코드를 짰습니다. C로 인접행렬 크기 20000*20000으로 잡으면 메모리 초과가 나는것 같아서.. vector를 이용했습니다. 각 정점으로 이동할 때 마다 1또는 2로 check번호를 매겨서 검사를 할때 인접한 정점과 check번호가 같은 정점이 발견되면 이분그래프가 아닌것이 되겠죠?

#include <vector>
#include <iostream>
 
using namespace std;
 
vector<vector<int> > graph;
int V, E;
vector<bool> visited;
vector<int> check;
 
bool biCheck() {
    for (int r = 0; r < V; r++) {  //전체 검사
        int curSize = graph[r].size();  //현재 정점에서 이동할 수 있는 갯수
        for (int c = 0; c < curSize; c++) {
            if (check[graph[r][c]] == check[r]) return false;  //인접한 정점과 구분한
        }                                                       //기준과 같으면 return false
    }
    return true;  //검사가 끝나면 return true
}
 
void dfs(int cur, int bi) {  //모든 정점은 1또는 2
    visited[cur] = true; check[cur]=bi % 2 + 1;  //방문체크 후 정점에 대한 구분
    int curSize = graph[cur].size();  //현재정점에서 이동할 수 있는 갯수
    for (int i = 0; i < curSize; i++) {
        int target = graph[cur][i];  //정점에서 이동할 정점
        if (!visited[target]) {  //방문하지 않았다면
            dfs(target, bi + 1); //탐색
        }
    }
}
 
int main(void) {
    int testCase;
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        cin >> V >> E;
        graph.resize(V);
        visited.resize(V);
        check.resize(V);
        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            graph[u - 1].push_back(v - 1);
            graph[v - 1].push_back(u - 1);
        }
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(i, 0);
        }
 
        if (biCheck()) cout << "YES\n";
        else cout << "NO\n";
        graph.clear();
        visited.clear();
        check.clear();
    }
 
    return 0;
}