문제

16168번: 퍼레이드

풀이

같은 간선을 두 번 이상 지나지 않으면서 모든 간선을 지나는 문제 즉, 오일러 경로에 대한 문제이다.
중복 없이 모든 간선을 지나기 위해서는 그래프의 각 노드들의 차수를 확인해야 한다.

이 문제는 무향 그래프에 관한 문제이기 때문에 노드의 차수가 짝수이어야 한다.
하지만 시작 노드와 도착 노드가 같지 않아도 되기 때문에
시작 노드와 도착 노드가 다르다면 시작과 도착 노드의 차수는 홀수가 되는 경우가 있다.

각 노드가 하나의 집합으로 되어있지 않다면 모든 노드를 탐색할 수 없기때문에 이또한 불가능한 경우가 된다.
모든 노드가 하나의 집합으로 되어있는지 확인하기 위해서는 dfs, bfs 탐색을 활용해도 되고, union-find 알고리즘으로 집합을 확인해도 된다.

코드

#include <iostream>
#include <vector>

using namespace std;

int v, e;
vector<int> edgeCount;
vector<int> head;
vector<int> depth;

int find(int x){
    if (head[x] == x) return x;
    else return head[x] = find(head[x]);
}

void Union(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return;

    if (depth[x] < depth[y]){
        head[x] = y;
    }
    else if (depth[x] > depth[y]){
        head[y] = x;
    }
    else {
        head[x] = y;
        depth[y]++;
    }
}

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

    cin >> v >> e;
    edgeCount.assign(v+1, 0);
    head.assign(v+1, 0);
    for (int i=0; i<v+1; i++) head[i] = i;
    depth.assign(v+1, 0);

    for (int i=0; i < e; i++){
        int a, b;
        cin >> a >> b;
        edgeCount[a]++;
        edgeCount[b]++;
        Union(a, b);
    }
    
    string answer = "NO";
    bool isSingle = true;
    for (int i=1; i < v; i++){
        if (find(i) != find(i+1)) isSingle = false;
    }

    if (isSingle){
        int oddCount = 0;
        for (int i=1; i < v+1; i++){
            if (edgeCount[i] % 2 != 0) oddCount++;
        }
        if (oddCount == 0 || oddCount == 2) answer = "YES";
    }

    cout << answer << endl;
    return 0;
}

참고

오일러 경로 참고
https://algorfati.tistory.com/140