오일러 경로와 회로

오일러 경로 / 회로

그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 오일러 경로(Eulerian
trail), 시작점과 끝점이 같은 것을 오일러 회로(Eulerian circuit) 라 한다.
"한붓그리기"가 가능한가를 묻는 고전 문제다.

존재 조건

연결성(간선이 있는 정점들이 한 덩어리)을 전제로 한다.

무방향 그래프

홀수 차수 정점이 2개면 그 둘이 각각 시작점과 끝점이 된다.

방향 그래프

왜 짝수 차수인가

회로가 어떤 정점을 지날 때마다 "들어오는 간선 하나, 나가는 간선 하나"를 짝지어
쓴다. 모든 간선을 정확히 한 번씩 쓰고 시작점으로 돌아오려면, 각 정점에서 쓰인
간선이 짝을 이뤄야 하므로 차수가 짝수여야 한다. 시작점과 끝점이 다른 경로라면
그 두 곳에서만 짝이 하나 어긋나므로 홀수 차수가 정확히 2개가 된다.

히어홀처 알고리즘

조건을 만족하면 다음 방식으로 실제 회로를 \(O(E)\)에 구성한다.

1. 시작 정점에서 출발해 아직 안 쓴 간선을 따라 임의로 진행하다가 더 갈 수
   없으면 멈춘다. 회로라면 이 막다른 곳은 반드시 출발점이다.
2. 만들어진 경로 위에서, 아직 안 쓴 간선이 남은 정점을 찾아 거기서 다시
   같은 방식으로 작은 회로를 만들어 끼워 넣는다.
3. 모든 간선을 쓸 때까지 반복한다.

핵심 구현 트릭은 각 정점마다 "다음에 볼 간선 위치(포인터)"를 두어 같은 간선을
다시 보지 않게 하고, DFS 후위 순서로 정점을 스택에 쌓아 뒤집는 것이다.
이렇게 하면 끼워 넣기를 명시적으로 하지 않고도 올바른 순서가 나온다.

복잡도

각 간선을 정확히 한 번 소비하므로 \(O(V + E)\)다. 단, 무방향 그래프는 간선을
양끝에서 동시에 "사용됨" 표시해야 한다.

방향 그래프 오일러 회로 구현

각 정점의 인접 리스트에 진행 포인터 ptr를 두어 쓴 간선을 건너뛴다.
후위 순서로 쌓은 결과를 뒤집으면 회로가 된다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1001;
vector<int> g[MAXN];   // 진출 간선의 도착 정점들
int ptr_[MAXN];        // 각 정점에서 다음에 볼 간선 인덱스
vector<int> circuit;   // 결과(역순으로 쌓임)

void hierholzer(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top();
        if (ptr_[u] < (int)g[u].size()) {
            int v = g[u][ptr_[u]++];   // 안 쓴 간선을 따라간다
            st.push(v);
        } else {
            circuit.push_back(u);       // 더 못 가면 후위 순서로 기록
            st.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        g[a].push_back(b); outdeg[a]++; indeg[b]++;
    }
    // 회로 존재 조건: 모든 정점 indeg == outdeg, 그리고 연결성 확인 필요
    hierholzer(1);
    // circuit이 간선 수 + 1 길이면 성공
    return 0;
}

무방향 그래프라면 간선마다 "사용됨" 플래그를 두고, 양방향 인접 리스트에서 한
간선을 쓸 때 반대편 복제 간선도 동시에 사용 표시해야 한다. 보통 간선 번호와
짝 간선 번호(eid ^ 1)로 관리한다.

흔한 실수

• 재귀 DFS 사용 — 간선이 많으면 재귀 깊이가 폭발한다. 위처럼 명시적
  스택으로 구현하는 것이 안전하다.
• 무방향 양쪽 표시 누락 — 한 간선을 한 번만 써야 하므로 양 끝 모두 사용
  표시해야 한다. 안 그러면 같은 간선을 두 번 쓴다.
• 연결성 미확인 — 차수 조건만 보면 안 된다. 간선이 있는 정점들이 하나의
  컴포넌트인지 별도로 확인해야 한다(고립 정점은 무시 가능).
• 결과 길이 검증 — 만든 경로의 간선 수가 전체 간선 수와 같아야 진짜
  오일러 경로다.

응용

대표 응용인 드 브루인 수열은 모든 길이-\(k\) 패턴을 정확히 한 번씩 포함하는
순환 문자열로, \(k-1\) 글자를 정점으로 두고 한 글자 확장을 간선으로 둔 그래프의
오일러 회로로 구성한다. 오일러 경로는 "간선을 빠짐없이 한 번씩"이라는 제약을
가진 구성 문제 전반에서 강력한 도구다.