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

1707번: 이분 그래프

이분 그래프를 dfs를 이용하여 나타내었다. 먼저 간선에 대한 정보를 벡터에 입력받아 저장해준 후 벡터 전체를 돌며 color가 0인 경우 dfs를 돌려주었다. dfs는 백터를 따라 색을 칠해주게 되는데 1과 -1을 번갈아가며 칠해준다. 반복문을 마치고 인접한 두 정점의 색이 같을 경우 NO를 출력하고 아닌 경우 YES를 출력해주었다.
이분 그래프를 찾는 방식을 구글을 찾아보고 알게 되었다. 기억해두자.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int K, V, E;
vector<int> v[20001];
int color[20001];

void dfs(int n, int c) {
    color[n] = c;

    for (int i = 0; i < v[n].size(); i++) {
        int next = v[n][i];

        if (color[next] == 0) {
            dfs(next, c * -1);
        }
    }
}

bool isTrue() {
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            int next = v[i][j];

            if (color[i] == color[next]) {
                return false;
            }
        }
    }

    return true;
}

void solution() {
    for (int i = 1; i <= V; i++) {
        if (color[i] == 0) {
            dfs(i, 1);
        }
    }

    if (isTrue()) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> K;

    while (K--) {
        memset(color, 0, sizeof(color));
        
        for (int i = 0; i < 20001; i++) {
            v[i].clear();
        }

        cin >> V >> E;

        for (int i = 0; i < E; i++) {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }

        solution();
    }

    return 0;
}