「学习笔记」基环树

众所周知，一棵有 \(n\) 个节点的树有 \(n – 1\) 条边，树上没有环。
据此，明显的，对于一个有 \(n\) 个结点 \(n\) 条边的无向连通图，必定是在一棵树上的任意两个节点之间连一条边构成的。我们把 \(n\) 个节点 \(n\) 条边的无向连通图，就称为基环树。

基环树上存在环，因此基环树它不是树，而是图。基环树又称章鱼图。

如图，这就是一棵基环树。
如果一张有向弱连通图每个点的入度都为 \(1\)，则称它是一棵 基环外向树，如下图。

如果一张有向弱连通图每个点的出度都为 \(1\)，则称它是一棵 基环内向树，如下图。

多棵树可以组成一个森林，多棵基环树可以组成基环森林，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成基环内向森林。

找环

基环树的的特别之处就在于这个环，因此，大部分基环树题目中，找环是十分必要的。
在简单图中，可以利用 dfs 的天然栈性质来找环，具体实现方式与 tarjan 求强连通分量很相似。

void getloop(int u) {
dep[u] = dep[fa[u]] + 1;
for (int v : e[u]) {
if (v == fa[u]) continue ;
if (!dep[v]) {
fa[v] = u;
getloop(v);
}
else if (dep[v] < dep[u]) {
for (int i = u; ; i = fa[i]) {
ok[i] = 1;
loop[++ m] = i;
if (i == v) {
break;
}
}
}
}
}


再有重边的图中，需要做一下小小的处理，与 tarjan 求双连通分量很像，记录一下边的编号，只要不走回刚走过来的边就行。

vector<pair<int, int> > e[N];

void getloop(int u, int i) {
dep[u] = dep[fa[u]] + 1;
for (auto it : e[u]) {
int v = it.first, k = it.second;
if (k == i) continue;
if (!dep[v]) {
fa[v] = u;
getloop(v, k);
}
else if (dep[v] < dep[u]) {
for (int j = u; ; j = fa[j]) {
ok[j] = 1;
loop[++ m] = j;
if (i == v) {
break;
}
}
}
}
}


练习

基环树题目中，较常见的 套路 思路就是先将环去掉，对每一棵树做处理，最后再对环做处理。

P8943 Deception Point

这是一道基础的入门题。
我们发现，只要两个人能在到达环上之前不碰面（包括刚到达环上），那雷切尔就一定存活 秦王绕柱，否则就必死无疑，处理三角洲到达环上的距离与雷切尔到达环上的距离，再查看是否会在到达环上是碰面即可。

/*
The code was written by yifan, and yifan is neutral!!!
*/

int main() {
n = read<int>(), q = read<int>();
for (int i = 1, x, y; i <= n; ++ i) {
x = read<int>(), y = read<int>();
e[x].emplace_back(y);
e[y].emplace_back(x);
}
getloop(1);
memset(dep, 0, sizeof dep);
for (int i = 1; i <= m; ++ i) {
dfs(loop[i], 0, i);
// cout << loop[i] << ' ';
}
while (q --) {
int x = read<int>(), y = read<int>();
int d1 = dep[x], t1 = top[x];
int d2 = dep[y], t2 = top[y];
if (d2 + min(abs(t1 - t2), m - abs(t1 - t2)) > d1) {
puts("Survive");
}
else {
puts("Deception");
}
}
return 0;
}


P8655 [蓝桥杯 2017 国 B] 发现环

简单的找环模板 = =||

/*
The code was written by yifan, and yifan is neutral!!!
*/

int main() {
n = read<int>();
for (int i = 1, x, y; i <= n; ++ i) {
x = read<int>(), y = read<int>();
e[x].emplace_back(y);
e[y].emplace_back(x);
}
getloop(1);
for (int i = 1; i <= n; ++ i) {
if (ok[i]) {
printf("%d ", i);
}
}
return 0;
}


P6037 Ryoku 的探索

朴素做法为 \(O_{n^2}\) 的。
但仔细观察，就会发现，最终答案一定是除去环上一条边，其他边的长度总和，删掉哪条边呢？根据美观度来判断。

/*
The code was written by yifan, and yifan is neutral!!!
*/

int main() {
n = read<int>();
for (int i = 1, x, y; i <= n; ++ i) {
x = read<int>(), y = read<int>();
ll w = read<ll>(), q = read<ll>();
e[x].emplace_back(y, w, q);
e[y].emplace_back(x, w, q);
}
getloop(1);
for (int i = 1; i <= m; ++ i) {
dfs(loop[i], 0, loop[i]);
}
loop[m + 1] = loop[1];
for (int i = 1; i <= m; ++ i) {
for (node it : e[loop[i]]) {
int v = it.v;
if (v == loop[i + 1]) {
dis[i] = it.w;
sum += it.w;
break;
}
}
}
for (int i = 1, u; i <= n; ++ i) {
u = top[i];
ll W = 0, P = 1e9;
for (node it : e[u]) {
int v = it.v;
ll w = it.w, p = it.p;
if (!ok[v]) continue;
if (p < P) {
W = w;
P = p;
}
}
printf("%lld\n", sum - W + ans);
}
return 0;
}


__EOF__

本文作者： yi_fan0305

本文链接： https://www.cnblogs.com/yifan0305/p/17506679.html

关于博主： 四叶草少年

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

声援博主： 如果您觉得文章对您有帮助，可以点击文章下方的【推荐】一下。