「学习笔记」基环树 环球新消息

众所周知，一棵有 \(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 > 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 using namespace std;typedef long long ll;templateinline 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 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(), q = read();for (int i = 1, x, y; i <= n; ++ i) {x = read(), y = read();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(), y = read();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 using namespace std;typedef long long ll;templateinline 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 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();for (int i = 1, x, y; i <= n; ++ i) {x = read(), y = read();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 using namespace std;typedef long long ll;templateinline 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 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();for (int i = 1, x, y; i <= n; ++ i) {x = read(), y = read();ll w = read(), q = read();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;}