백준 16168번 퍼레이드 C++

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

16168번: 퍼레이드

 

오일러경로 : 노드가 전부 연결되어있고 차수가 홀수인 노드가 0개 또는 2개이라면 한 경로를 한번만 들려서 모든 경로를 돌 수 있다.

 

#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;

int n, e;
vector<int> parent;
vector<int> height;
vector<int> chasu;

int GetParent(int a) {
    if (a == parent[a]) return a;
    return GetParent(parent[a]);
}

void Merge(int u, int v) {
    u = GetParent(u);
    v = GetParent(v);

    if (u == v) return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

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

    cin >> n >> e;
    parent = vector<int>(n + 1);
    height = vector<int>(n + 1, 1);
    chasu = vector<int>(n + 1, 0);
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 0; i < e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        chasu[v1]++;
        chasu[v2]++;
        Merge(v1, v2);
    }
    set<int> s;
    for (int i = 1; i <= n; i++) {
        int parent = GetParent(i);
        s.insert(parent);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (chasu[i] % 2 == 0) continue;
        cnt++;
    }
    if (s.size() == 1 && (cnt == 0 || cnt == 2)) {
        cout << "YES";
    }
    else cout << "NO";
}