1707 이분 그래프

링크

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

채점 현황

전체 소스 코드

#include <iostream>
#include <vector>
using namespace std;

int T, V, E;
vector<vector<int>> arr;
bool check[20002];
bool colorCheck[20002];
int color[20002];

void paintColor(int cnt, int cntColor) {
    for (int i = 0; i < arr[cnt].size(); i++) {
        int next = arr[cnt][i];
        if (check[next] == false) {
            if (cntColor == 1) {
                color[next] = 2;
                check[next] = true;
                paintColor(next, 2);
            } else {
                color[next] = 1;
                check[next] = true;
                paintColor(next, 1);
            }
        }
    }
}

bool confirmColor(int cnt) {
    bool isTrue = true;

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

        if (color[cnt] != color[next]) {
            if (colorCheck[next] == false) {
                colorCheck[next] = true;
                isTrue = confirmColor(next);
            }
        } else {
            return false;
        }
    }

    return isTrue;
}

int main(void) {
    cin >> T;

    while (T--) {
        cin >> V >> E;
        arr = vector<vector<int>>(V + 1);

        for (int i = 0; i < E; i++) {
            int x, y;
            cin >> x >> y;

            arr[x].push_back(y);
            arr[y].push_back(x);
        }

        for (int i = 1; i <= V; i++) {
            if (check[i] == false) {
                check[i] = true;
                color[i] = 1;
                paintColor(i, 1);
            }
        }

        bool isTrue;
        for (int i = 1; i <= V; i++) {
            if (colorCheck[i] == false) {
                colorCheck[i] = true;
                isTrue = confirmColor(i);

                if (isTrue == false) {
                    cout << "NO" << '\n';
                    break;
                }
            }
        }
        if (isTrue == true) {
            cout << "YES" << '\n';
        }

        for (int i = 1; i <= V; i++) {
            check[i] = 0;
            colorCheck[i] = false;
            color[i] = 0;
        }
    }
}