E044. Нахождение Эйлерова пути за O (M)
Источник: e-maxx.ru/algo, страница PDF 134.
Эйлеров путь - это путь в graphе, проходящий через все его рёбра. Эйлеров цикл - это эйлеров путь, являющийся циклом. Task заключается в том, чтобы find эйлеров путь в неориентированном мультиgraphе с петлями.
Algorithm
Сначала проверим, существует ли эйлеров путь. Затем найдём все простые циклы и объединим их в один - это и будет эйлеровым циклом. Если graph таков, что эйлеров путь не является циклом, то, добавим недостающее edge, найдём эйлеров цикл, потом удалим лишнее edge. Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла). Кроме того, конечно, graph должен быть достаточно связным (т.е. если удалить из него все изолированные вершины, то должен получиться связный graph). Искать все циклы и объединять их будем одной рекурсивной процедурой:
procedure FindEulerPath (V)
1. перебрать все рёбра, Outputящие из вершины V;
каждое такое edge удаляем из graphа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ. Complexity этого Algorithmа, очевидно, является линейной относительно числа рёбер. Но этот же Algorithm мы можем записать в нерекурсивном варианте:
stack St;
в St кладём любую вершину (стартовая vertex);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое edge, Outputящее из V;
удаляем его из graphа;
второй конец этого ребра кладём в St;
Несложно проверить эквивалентность этих двух форм Algorithmа. Однако вторая форма, очевидно, быстрее работает, причём кода будет не больше.
Task о домино
Приведём здесь классическую задачу на эйлеров цикл - задачу о домино. Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). it is required выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать. Переформулируем задачу. Пусть числа, записанные на донимошках, - вершины graphа, а доминошки - рёбра этого graphа (каждая доминошка с числами (a,b) - это ребра (a,b) и (b,a)). Тогда наша Task сводится к задаче нахождения эйлерова пути в этом graphе.
Implementation
Приведенная ниже программа ищет и выводит эйлеров цикл или путь в graphе, или выводит -1, если его не существует. Сначала программа проверяет степени вершин: если вершин с нечётной степенью нет, то в graphе есть эйлеров цикл, если есть 2 вершины с нечётной степенью, то в graphе есть только эйлеров путь (эйлерова цикла нет), если же таких вершин больше 2, то в graphе нет ни эйлерова цикла, ни эйлерова пути. Чтобы find эйлеров путь (не цикл), поступим таким образом: если V1 и V2 - это две вершины нечётной степени, то просто добавим edge (V1,V2), в полученном graphе найдём эйлеров цикл (он, очевидно, будет существовать), а затем удалим из ответа "фиктивное" edge (V1,V2). Эйлеров цикл будем искать в точности так, как описано выше (нерекурсивной версией), и заодно по окончании этого Algorithmа проверим, связный был graph или нет (если graph был не связный, то по окончании работы Algorithmа в graphе останутся некоторые рёбра, и в этом случае нам надо вывести -1). Наконец, программа учитывает, что в graphе могут быть изолированные вершины.
int main() {int n;vector < vector<int> > g (n, vector<int> (n));
... чтение graphа в матрицу смежности ...
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 (!deg[first]) ++first;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)puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)printf ("%d ", res[i]+1);
}
C# solution
auto-draft, review before submitusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
procedure FindEulerPath (V)
1. перебрать все рёбра, выходящие из вершины V;
каждое такое ребро удаляем из графа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ.
stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
второй конец этого ребра кладём в St;
int main() {
int n;
vector < List<int> > g (n, List<int> (n));
... чтение графа в матрицу смежности ...
List<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 (!deg[first]) ++first;
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);
List<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)
{
List<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)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
Console.Write ("%d ", res[i]+1);
}
}C++ solution
matched/originalprocedure FindEulerPath (V)
1. перебрать все рёбра, выходящие из вершины V;
каждое такое ребро удаляем из графа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ.
stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
второй конец этого ребра кладём в St;
int main() {
int n;
vector < vector<int> > g (n, vector<int> (n));
... чтение графа в матрицу смежности ...
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 (!deg[first]) ++first;
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)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
printf ("%d ", res[i]+1);
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
procedure FindEulerPath (V)
1. перебрать все рёбра, выходящие из вершины V;
каждое такое ребро удаляем из графа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ.
stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
второй конец этого ребра кладём в St;
int main() {
int n;
vector < ArrayList<Integer> > g (n, ArrayList<Integer> (n));
... чтение графа в матрицу смежности ...
ArrayList<Integer> 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 (!deg[first]) ++first;
int v1 = -1, v2 = -1;
boolean 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);
ArrayList<Integer> 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)
{
ArrayList<Integer> 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)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
System.out.print ("%d ", res[i]+1);
}
}Материал разбит как Algorithmическая Task: изучить постановку, понять асимптотику и реализовать Algorithm на выбранном языке.
Vacancies for this task
Active vacancies with overlapping task tags are shown.