오일러 회로

백준 1199번: 오일러 회로

아이디어

모든 간선을 딱 한 번씩만 사용해서 원점으로 돌아올 수 있으면 오일러 회로다. 오일러 회로는 모든 노드에 연결된 간선의 개수가 짝수여야만 한다.

오일러 회로를 구하기 위해 Hierholzer's Algorithm을 알아보자.

a에서 시작해 a로 돌아오는 회로를 그려야 한다. 그리다가 중간에 회로에 포함되지 않은 간선을 가지고 있는 노드랑 만나면, 그 간선을 타고 가서 회로를 만들고, 다시 돌아온다. 이를 재귀적(DFS)으로 구현할 수 있다.
노드에 존재하는 간선을 만날 때마다 타고가면서 간선을 지우고 다음 노드로 함수를 호출한다. 함수 종료 시점에 노드를 출력하면 오일러 회로 완성!

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1001;
int N;
stack<int> adj[MAX];
int edges[MAX][MAX];
int degree[MAX];

void euler(int n) {
    while (!adj[n].empty()) {
        int next = adj[n].top();
        adj[n].pop();
        if (edges[n][next] && edges[next][n]) {
            edges[n][next]--;
            edges[next][n]--;
            euler(next);
        }
    }
    cout << n << ' ';
}

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

    cin >> N;
    for (int i = 1; i < N+1; i++) {
        for (int j = 1; j < N+1; j++) {
            int x;
            cin >> x;
            while (x--) {
                adj[i].push(j);
                edges[i][j]++;
                degree[j]++;
            }
        }
    }
    // 간선 홀수개 있으면 오일러 회로 완성 불가
    for (int i = 1; i < N+1; i++) {
        if (degree[i]%2) {
            cout << -1;
            return 0;
        }
    }

    euler(1);

    return 0;
}

여담

시간복잡도를 줄이기 위해 스택에 간선을 저장해놓고, 이미 본 간선은 pop해서 다시 안보도록 했다. 넘 어렵다.