「学习笔记」基环树
众所周知，一棵有 \(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!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2e5 + 5;
int n, q, m;
int dep[N], top[N], fa[N], loop[N], dis[N];
bool ok[N];
vector<int> e[N];
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;
}
}
}
}
void dfs(int u, int fat, int tp) {
top[u] = tp;
for (int v : e[u]) {
if (v == fat || ok[v]) continue ;
dep[v] = dep[u] + 1;
dfs(v, u, tp);
}
}
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!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1e5 + 5;
int n;
int dep[N], fa[N];
bool ok[N];
vector<int> e[N];
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;
if (i == v) break;
}
}
}
}
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!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1e6 + 5;
int n, m;
ll ans, sum;
int loop[N], top[N], fa[N], dep[N];
ll dis[N];
bool ok[N];
struct node {
int v;
ll w, p;
node(int a, ll b, ll c): v(a), w(b), p(c) {};
};
vector<node> e[N];
void getloop(int u) {
dep[u] = dep[fa[u]] + 1;
for (node it : e[u]) {
int v = it.v;
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;
}
}
}
}
void dfs(int u, int fat, int tp) {
top[u] = tp;
for (node it : e[u]) {
int v = it.v;
ll w = it.w;
if (v == fat || ok[v]) continue;
ans += w;
dfs(v, u, tp);
}
}
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;
}
朝气蓬勃 后生可畏