Вспомним обычный поиск в глубину. Он рекурсивно обходит весь граф, и посещает каждую вершину ровно один раз. Посещенные вершины при этом отмечаются в массиве used.
Давайте его немного модифицируем, а именно, давайте сохраним в какой-нибудь массив, в каком порядке мы посещали вершины. Есть два способа это сделать - посчитать время входа DFS-а в каждую вершину и время выхода.
Давайте назовем массивы $\space{\rm tin}$ и ${\rm tout}$, где ${\rm tin}$ - время входа, а $\space{\rm tout}$ - время выхода из вершины.
Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины:
int timer = 0;
void dfs (int v) {
tin[v] = timer++;
for (int i = 0; i < g[v].size(); ++i) {
if (!used[g[v][i]]) {
dfs(g[v][i]);
}
}
tout[v] = timer++;
}
Время входа или выхода пригождается во многих алгоритмах, давайте разберем несколько.
Пусть дан связный неориентированный граф. Мост - ребро, при удалении которой граф становится несвязным.
Первым делом введем новые виды ребер :
1) Ребра самого ДФС (tree edge или ребро дерева).
2) Ребра не посещенные в ДФС (back edge или. обратное ребро).
Пусть есть ребро $u \rightarrow v$, в каком случае оно является мостом, понятно, что обратное ребро не может быть мостом, потому что мы уже посещали обе вершины и следовательно есть путь по ребрам самого ДФС. Теперь разберемся с ребрами ДФС. Они являются мостом, только если нет пути по обратным ребрам в какого-то из предков $v$. Так как иначе мы можем удалить это ребро, но при этом останется путь по обратным ребрам.
Давайте докажем, что если путь до предка существует, то существует и путь, такой, что нам достаточно пройти по одному обратному ребру. Пусть такого пути не существует, но при этом есть какой-то путь из $n$ обратных ребер, тогда давайте посмотрим куда могут вести эти ребра, они могут вести либо в поддерево вершины $u$, либо в нее саму, либо в наддерево, в случае поддерева или самой вершины мы можем их убрать, так как есть путь по ребрам ДФС, в случае наддерева же нам достаточно сохранить только одно ребро в наддерево.
Тогда давайте введем $dp_{i}$ - минимальный $\space{\rm tin}$ такой вершины, до которой мы можем добраться за какое-то количество ребер ДФС и одно обратное. Как его пересчитывать. Очень просто : у нас есть три возможных значения динамики.
1) $dp_{i} = min(tin_{i}, dp_{i})$
2) $dp_{i} = min(dp_{i}, dp_{son})$, где $son$ - сын $i$-й вершины
3) $dp_{i} = min(dp_{i}, tin_{back})$, где $back$ - вершина, для которой есть обратное ребро из $i$-й вершины.
Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.
int timer, tin[MAXN], dp[MAXN];
void dfs(int u, int p) {
used[u] = true;
tin[u] = dp[v] = timer++;
for (auto to : g[v]) {
if (to == p) {
continue;
}
if (used[to]) {
dp[u] = min(dp[u], tin[to]);
}
else {
dfs(to, u);
dp[u] = min(dp[u], dp[to]);
}
if (dp[to] > tin[u]) {
//ребро - мост
}
}
}
Точка сочленения - вершина, при удалении которой граф становится несвязным.
Первое, что надо заметить, что мост и точка сочленения очень похожи, а что если они и ищутся одинаково. Давайте подумаем, что такое точка сочленения в рамках обратных ребер, это вершина у которой можно добраться до предка используя обратные и ребра ДФС вниз. Но тогда как изменится нахождение точек сочленения, единственное отличие, что у мостов надо было чтобы у предка было время входа строго больше, сейчас же нам достаточно и нестрогого неравенства, так как если из вершины можно добраться до нее самой, то она все равно точка сочленения. Также вылезает один крайний случай, а именно корень, так как в корень мы всегда войдем раньше других вершин, но тут решение очень простое, давайте посмотрим, сколько несвязных поддеревьев у корня.
int timer, tin[MAXN], dp[MAXN];
void dfs(int u, int p = -1) {
used[u] = 1;
tin[u] = dp[u] = timer++;
int children = 0;
for (auto to : g[u]) {
if (to == p) {
continue;
}
if (used[to]) {
dp[u] = min(dp[u], tin[to]);
}
else {
dfs(to, u);
dp[u] = min(dp[u], dp[to]);
}
if (dp[to] >= tin[u] && p != -1) {
//v - точка сочленения;
}
++children;
}
if (p == -1 && children > 1) {
//u - точка сочленения;
}
}
Эйлеров путь - это путь в графе, проходящий через все его рёбра. Эйлеров цикл - это эйлеров путь, являющийся циклом.
Научимся понимать, есть ли эйлеров цикл/путь в графе, давайте считать, что граф неориентированный. Изначально поймем, что граф должен состоять из одной компоненты и может содержать изолированные вершины.
Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой.
Пусть дан неориентированный связный цикл. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла).
Кстати, аналогичная теорема есть и для ориентированного графа (можете сами попытаться сформулировать).
Доказать это можно например через лемму о рукопожатиях.
Как теперь мы будем решать задачу нахождения цикла в предположении, что он точно есть. Давайте запустимся из произвольной вершины, пройдем по любому ребру и удалим его.
void findeulerpath(int v){
stack<pair<int, int> >s;
s.push({v, -1});
while (!s.empty()) {
v = s.top().first;
int x = s.top().second;
for (int i = 0; i < g[v].size(); i++){
pair<int, int> e = g[v][i];
if(!u[e.second]){
u[e.second]=1;
s.push(e);
break;
}
}
if (v == s.top().first) {
if (~x) {
p.push_back(x);
}
s.pop();
}
}
}