백준 1707번 이분 그래프 C++

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

 

처음에는 이분 그래프가 뭔지 몰라서 찾아봤더니 레드블랙 트리처럼 인접한 정점들이 다른 색으로 칠해져야 한다는 것을 알았다. dfs로 탐색하면서 방문 정보를 저장하는 배열에 색 정보도 같이 저장해서 인접한 정점들이 서로 다른 색일때는 YES, 아니면 NO를 출력했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

bool ans = true;

enum Color {
    Red,
    Black,
    Size
};

vector<vector<int>> graph;
vector<pair<bool, Color>> visited;

void Dfs(int vertex, Color color) {

    visited[vertex] = { true,color };

    Color nextColor;
    if (color == Red) nextColor = Black;
    else nextColor = Red;

    for (auto next : graph[vertex]) {
        if (visited[next].first) {
            if (visited[next].second == color)
                ans = false;
            continue;
        }
        Dfs(next, nextColor);
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        ans = true;
        int v, e;
        cin >> v >> e;
        graph = vector<vector<int>>(v + 1, vector<int>());
        visited = vector<pair<bool, Color>>(v + 1, { false,Size });
        for (int i = 0; i < e; i++) {
            int start, end;
            cin >> start >> end;
            graph[start].push_back(end);
            graph[end].push_back(start);
        }
        for (int i = 1; i <= v; i++) {
            if (visited[i].first) continue;
            Dfs(i, Red);
        }
        if (ans) cout << "YES";
        else cout << "NO";
        cout << "\n";
    }
}