$O(M)$ 시간에 오일러 경로 찾기¶
오일러 경로는 그래프의 모든 간선을 정확히 한 번씩 지나는 경로입니다. 오일러 사이클은 사이클인 오일러 경로입니다.
이 문제는 루프가 있는 무방향 멀티그래프에서 오일러 경로를 찾는 것입니다.
알고리즘¶
먼저 오일러 경로가 존재하는지 확인할 수 있습니다. 다음 정리를 사용할 수 있습니다. 오일러 사이클은 모든 정점의 차수가 짝수일 때, 그리고 그때에만 존재합니다. 그리고 오일러 경로는 홀수 차수를 갖는 정점의 수가 2개(또는 오일러 사이클이 존재하는 경우에는 0개)일 때, 그리고 그때에만 존재합니다. 물론 이에 더해 그래프는 충분히 연결되어 있어야 합니다(즉, 그래프에서 고립된 정점을 모두 제거하면 연결 그래프가 되어야 합니다).
오일러 경로 / 오일러 사이클을 찾기 위해 다음 전략을 사용할 수 있습니다: 모든 단순 사이클을 찾아 하나로 합칩니다. 이것이 오일러 사이클이 됩니다. 그래프의 오일러 경로가 사이클이 아닌 경우에는 빠진 간선을 추가하고 오일러 사이클을 찾은 다음, 추가한 간선을 제거합니다.
모든 사이클을 찾아 합치는 작업은 간단한 재귀 절차로 수행할 수 있습니다:
procedure FindEulerPath(V)
1. iterate through all the edges outgoing from vertex V;
remove this edge from the graph,
and call FindEulerPath from the second end of this edge;
2. add vertex V to the answer.
이 알고리즘의 복잡도는 분명히 간선 개수에 대해 선형입니다.
하지만 같은 알고리즘을 비재귀 버전으로도 작성할 수 있습니다:
stack St;
put start vertex in St;
until St is empty
let V be the value at the top of St;
if degree(V) = 0, then
add V to the answer;
remove V from the top of St;
otherwise
find any edge coming out of V;
remove it from the graph;
put the second end of this edge in St;
알고리즘의 이 두 형태가 동등하다는 것은 쉽게 확인할 수 있습니다. 하지만 두 번째 형태가 분명히 더 빠르며, 코드도 훨씬 더 효율적입니다.
도미노 문제¶
여기서는 고전적인 오일러 사이클 문제인 도미노 문제를 소개합니다.
$N$개의 도미노가 있으며, 잘 알려져 있듯이 도미노의 양 끝에는 각각 숫자가 하나씩 적혀 있습니다(보통 1부터 6까지이지만, 여기서는 중요하지 않습니다). 인접한 두 도미노의 맞닿은 쪽에 적힌 숫자가 서로 일치하도록 모든 도미노를 한 줄로 놓으려고 합니다. 도미노는 돌려 놓을 수 있습니다.
문제를 다시 정식화해 봅시다. 도미노에 적힌 숫자들을 그래프의 정점으로, 도미노를 이 그래프의 간선으로 둡니다(숫자 $(a,b)$가 적힌 각 도미노는 간선 $(a,b)$와 $(b,a)$입니다). 그러면 이 문제는 이 그래프에서 오일러 경로를 찾는 문제로 환원됩니다.
구현¶
아래 프로그램은 그래프에서 오일러 사이클 또는 경로를 찾아 출력하며, 존재하지 않으면 $-1$을 출력합니다.
먼저 프로그램은 정점의 차수를 확인합니다. 홀수 차수를 갖는 정점이 없으면 그래프에 오일러 사이클이 있고, 홀수 차수를 갖는 정점이 $2$개이면 그래프에는 오일러 경로만 있으며(오일러 사이클은 없음), 그러한 정점이 $2$개보다 많으면 그래프에는 오일러 사이클도 오일러 경로도 없습니다. 오일러 경로(사이클이 아닌 것)를 찾기 위해 다음과 같이 합시다. $V1$과 $V2$가 홀수 차수를 갖는 두 정점이라면 간선 $(V1, V2)$를 추가하고, 그 결과로 얻은 그래프에서 오일러 사이클을 찾은 다음(이 사이클은 당연히 존재합니다), 답에서 "가상의" 간선 $(V1, V2)$를 제거합니다. 오일러 사이클은 위에서 설명한 방식(비재귀 버전) 그대로 찾으며, 동시에 이 알고리즘의 끝에서 그래프가 연결되어 있었는지 확인합니다(그래프가 연결되어 있지 않았다면 알고리즘이 끝났을 때 그래프에 일부 간선이 남아 있게 되며, 이 경우 $-1$을 출력해야 합니다). 마지막으로, 프로그램은 그래프에 고립된 정점이 있을 수 있다는 점을 고려합니다.
이 문제에서는 인접 행렬을 사용한다는 점에 유의하십시오. 또한 이 구현은 다음 정점을 브루트포스로 찾기 때문에 행렬의 행 전체를 계속해서 반복하여 순회해야 합니다. 더 나은 방법은 그래프를 인접 리스트로 저장하고, 간선을 $O(1)$에 제거하며, 역방향 간선은 별도의 리스트에 표시하는 것입니다. 이렇게 하면 $O(M)$ 알고리즘을 얻을 수 있습니다.
int main() {
int n;
cin >> n;
vector<vector<int>> g(n, vector<int>(n));
// reading the graph in the adjacency matrix
vector<int> deg(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
deg[i] += g[i][j];
}
int first = 0;
while (first < n && !deg[first])
++first;
if (first == n) {
cout << -1;
return 0;
}
int v1 = -1, v2 = -1;
bool bad = false;
for (int i = 0; i < n; ++i) {
if (deg[i] & 1) {
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;
}
}
if (v1 != -1)
++g[v1][v2], ++g[v2][v1];
stack<int> st;
st.push(first);
vector<int> res;
while (!st.empty()) {
int v = st.top();
int i;
for (i = 0; i < n; ++i)
if (g[v][i])
break;
if (i == n) {
res.push_back(v);
st.pop();
} else {
--g[v][i];
--g[i][v];
st.push(i);
}
}
if (v1 != -1) {
for (size_t i = 0; i + 1 < res.size(); ++i) {
if ((res[i] == v1 && res[i + 1] == v2) ||
(res[i] == v2 && res[i + 1] == v1)) {
vector<int> res2;
for (size_t j = i + 1; j < res.size(); ++j)
res2.push_back(res[j]);
for (size_t j = 1; j <= i; ++j)
res2.push_back(res[j]);
res = res2;
break;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j])
bad = true;
}
}
if (bad) {
cout << -1;
} else {
for (int x : res)
cout << x << " ";
}
}