Author: ZYY
Date: 2025-05-09
tag: 基环树
C++的基环树
一 定义
《算法进阶指南》对于基环树给出了定义：
N个点的树有N - 1条边。若在树上任意添加一条边，则会形成一个环。这种N个点N条边的连通无向图称为基环树。
有点生涩难懂对吧，我们用简单的语言对它再进行解释
即在一棵树上加一条边之后，恰好变为包含一个环的图称为基环树
同时这是在加边后仍是连通图的前提下给出的定义 反之如果加边后的图不保证连通 那么我们引申出一个新的定义
N个点、N条边的不连通无向图也可能是若干棵基环树组成的森林，简称基环树森林
二 性质
(1) 从定义出发 因为树上不能包含环 我们发现基环树其实并不是一棵树
(2) 内向树与外向树
我们将每个点仅有一条出边的有向图称为内向树
我们将每个点仅有一条入边的有向图称为外向树
注： 我们将内向树和外向树都统一归纳为基环树。
这里为大家提供一幅图 对比了普通基环树，内向树，外向树
三 处理
基环树的结构虽然简单仅仅又一棵树再加一条边组成 但是处理起来还是有一定难度的 处理基环树的关键就在于如何找到环 接着我们就可以将环作为基环树的根节点 最后将除了环以外的树处理后再带着环一起计算
(1)对于无向图
1> 拓扑排序找环并记录环上的点
// 利用拓扑排序找环并记录环上所有点
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx; // 邻接表建图
int d[N]; // 记录入度
int ans[N]; // 记录环上点的编号
int cnt; // 记录环上点的个数
inline void add(int a, int b) { // 建图e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
queue<int> q;
inline void topsort() {for (int i = 1; i <= n; i++) { // 初始化入度if (!d[i]) {q.push(i);}}while (!q.empty()) {int t = q.front();q.pop();ans[cnt++] = t; // 记录环上点的编号for (int j = h[t]; j != -1; j = ne[j]) {int y = e[j];d[y]--;if (d[y] == 0) { // 如果入度为 0，加入队列q.push(y);}}}
}
int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;add(a, b); add(b, a);d[a]++, d[b]++;}topsort();for (int i = 0; i < cnt; i++) {cout << ans[i] << " "; // 输出环上点的编号}
}
2> Tarjan直接找环并标记环上的点
// DFS找环并记录环上的点
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], t, cnt; // dfn指的是dfs的顺序，low是能到达的最小的dfn
stack<int> stk;
bool in_stk[N]; // 记录栈中是否存在
vector<int> lex; // 记录环上的点inline void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}inline void Tarjan(int u, int fa) {dfn[u] = low[u] = ++t; // 初始化dfn和lowstk.push(u);in_stk[u] = true; for(int i = h[u]; ~i; i = ne[i]) {int v = e[i];if(v == fa) continue; // 如果是父节点就跳过if(!dfn[v]) { // 如果没有访问过Tarjan(v, u); low[u] = min(low[u], low[v]); } else if(in_stk[v]) {low[u] = min(low[u], dfn[v]);if(lex.empty()) {stack<int> lnx = stk; // 复制栈while(!lnx.empty() && lnx.top() != v) {lex.push_back(lnx.top());lnx.pop();}lex.push_back(v);}}}if(dfn[u] == low[u]) {while(!stk.empty()) {int v = stk.top();stk.pop();in_stk[v] = false;if(v == u) break;}}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for(int i = 0; i < m; i++) {int a, b;cin >> a >> b;add(a, b), add(b, a);}Tarjan(1, -1);for(int x : lex) {cout << x << " ";}cout << endl;return 0;
}对于有向图
拓扑排序只针对无向图 所以我们只能用Tarjan记录环
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], t;
stack<int> stk;
bool in_stk[N];
vector<int> lex;inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}inline void Tarjan(int u) {dfn[u] = low[u] = ++t;stk.push(u);in_stk[u] = true;for(int i = h[u]; ~i; i = ne[i]) {int v = e[i];if(!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if(in_stk[v]) {low[u] = min(low[u], dfn[v]);if(lex.empty()) {stack<int> lnx = stk;while(!lnx.empty() && lnx.top() != v) {lex.push_back(lnx.top());lnx.pop();}lex.push_back(v);}}}if(dfn[u] == low[u]) {while(!stk.empty()) {int v = stk.top();stk.pop();in_stk[v] = false;if(v == u) break;}}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for(int i = 0; i < m; i++) {int a, b;cin >> a >> b;add(a, b); }for(int i = 1; i <= n; i++) {if(!dfn[i]) Tarjan(i);}for(int x : lex) {cout << x << " ";}cout << endl;return 0;
}四 练习
Jouier
岛屿
创世纪
Freda的传呼机
双倍经验
岛屿
Freda的传呼机
创世纪
如果你想更强
如果你想变得更强 就多刷题吧
基环树题单
五，补充知识
在做岛屿时 我们会发现要求变化中的区间最值 我们这里补充一下单调队列这个知识点
从名字出发，单调是指保证区间内是单调递增/单调递减
队列是指具有队列的性质 即只能对队头/队尾进行操作
单调队列解决的主要问题是规定区间长度 求区间最值 我们一般选择在每一次更新区间时直接更换最大/最小值 这样可以保证时间复杂度最低
单调队列例题
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], n, k;void get_min() {int hh = 0, tt = -1;for(int i = 0; i < n; i++) {while(hh <= tt && i - k + 1 > q[hh]) hh++;while(hh <= tt && a[q[tt]] >= a[i]) tt--;q[++tt] = i;if(i >= k - 1) printf("%d ", a[q[hh]]);}puts("");
}void get_max() {int hh = 0, tt = -1;for(int i = 0; i < n; i++) {while(hh <= tt && i - k + 1 > q[hh]) hh++;while(hh <= tt && a[q[tt]] <= a[i]) tt--;q[++tt] = i;if(i >= k - 1) printf("%d ", a[q[hh]]);}puts("");
}int main() {scanf("%d%d", &n, &k);for(int i = 0; i < n; i++) scanf("%d", &a[i]);get_min();get_max();return 0;
}