算法 - Ear Decomposition (耳分解)

Ear decomposition 的定义见 Wikipedia。粗略地讲,在无向图中,耳朵就定义为一条路径,其中除了端点外的点的度数均为 2(端点可以重合),而且删去后不破坏图的连通性。耳分解就是将图中的耳朵依次删去直至删完,不是所有无向图都能被耳分解,同时耳分解的方案很可能是不唯一的。

充要条件

图中没有桥。必要性感受一下,还是显然的,证明就不证了。充分性可以用算法本身来证明,对于满足条件的无向图,算法一定能给出一个合法的耳分解。

算法

前置知识:理解 Tarjan 求桥。

大致的思路就是:在 DFS 树上切耳朵,同时保证每一次操作之后都不存在桥。

考虑 tarjan 过程中桥的判定条件,low[v] > dfn[u],为了保证在分解过程中始终满足没有桥的条件,就维护 low 的正确性。只需保留一个最小的 low 即可,其他的 low 的形成的链就删了(也就是 DFS 树上的回边(链)),如果有一个 low 保留下来了,那么相当于给它父亲的回边(链)上加了一个点(也就是如果哪一天,这个点提供的 low 不要了,就被和回边一起删掉了)。

于是呢,如果一开始不存在桥,那么分解的过程中也不会存在桥。当处理到树根的时候,一定会变成一个环,至此分解就成功了。

代码

AC 代码,虽然你可能找不到可以提交的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 2E4 + 100;
using VI = vector<int>;
vector<int> G[N];
int dfn[N], low[N], clk;
VI ears[N * 20];
int sz;
VI* cur[N];
vector<VI*> ans;

void dfs(int u, int fa) {
dfn[u] = low[u] = ++clk;
int _fst = 0;
vector<VI*> V;
for (int& v: G[u]) {
if (v == fa && ++_fst == 1) continue;
if (!dfn[v]) {
dfs(v, u);
if (low[v] > dfn[u]) { puts("-1"); exit(0); }
low[u] = min(low[u], low[v]);
cur[v]->push_back(u);
V.push_back(cur[v]);
} else if (dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
ears[sz].push_back(v);
ears[sz].push_back(u);
V.push_back(&ears[sz++]);
}
}
_fst = 0;
for (VI* x: V) {
int d = dfn[*x->begin()];
if (d > low[u] || (d == low[u] && ++_fst > 1)) {
ans.push_back(x);
} else cur[u] = x;
}
if (u == 1) ans.push_back(cur[u]);
}

int main() {
int n, m; cin >> n >> m;
FOR (_, 0, m) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
}
dfs(1, -1);
cout << ans.size() << endl;
for (VI* x: ans) {
printf("%d ", x->size() - 1);
FOR (i, 0, x->size()) printf("%d%c", x->at(i), i == _i - 1 ? '\n' : ' ');
}
}

后记

为什么要写这个呢?首先是因为在 2019 ByteDance ICPC Camp 中遇到了这样一道裸题,但是好像资料比较少,题解也不详细,所以就把解题过程记录一下。另外呢,掌握这个算法,对增加 Tarjan 的理解(主要是求桥)还是很有帮助的。