Solves

Appearance

Author: ZYY
Date: 2025-05-09
tag: 基环树

C++的基环树 ​

一 定义 ​

《算法进阶指南》对于基环树给出了定义：

N个点的树有N - 1条边。若在树上任意添加一条边，则会形成一个环。这种N个点N条边的连通无向图称为基环树。

有点生涩难懂对吧，我们用简单的语言对它再进行解释

即在一棵树上加一条边之后，恰好变为包含一个环的图称为基环树

同时这是在加边后仍是连通图的前提下给出的定义 反之如果加边后的图不保证连通 那么我们引申出一个新的定义

N个点、N条边的不连通无向图也可能是若干棵基环树组成的森林，简称基环树森林

二 性质 ​

(1) 从定义出发 因为树上不能包含环 我们发现基环树其实并不是一棵树 ​

(2) 内向树与外向树 ​

我们将每个点仅有一条出边的有向图称为内向树

我们将每个点仅有一条入边的有向图称为外向树

注： 我们将内向树和外向树都统一归纳为基环树。

这里为大家提供一幅图 对比了普通基环树，内向树，外向树

三 处理 ​

基环树的结构虽然简单仅仅又一棵树再加一条边组成 但是处理起来还是有一定难度的 处理基环树的关键就在于如何找到环 接着我们就可以将环作为基环树的根节点 最后将除了环以外的树处理后再带着环一起计算

(1)对于无向图 ​

1> 拓扑排序找环并记录环上的点 ​

cpp
// 利用拓扑排序找环并记录环上所有点
#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直接找环并标记环上的点 ​

cpp
// 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和low
    stk.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记录环 ​

cpp
#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的传呼机创世纪

如果你想更强 ​

如果你想变得更强 就多刷题吧 基环树题单

五，补充知识 ​

在做岛屿时 我们会发现要求变化中的区间最值 我们这里补充一下单调队列这个知识点

从名字出发，单调是指保证区间内是单调递增/单调递减队列是指具有队列的性质 即只能对队头/队尾进行操作

单调队列解决的主要问题是规定区间长度 求区间最值 我们一般选择在每一次更新区间时直接更换最大/最小值 这样可以保证时间复杂度最低

单调队列例题

language
#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;
}

Copyright © 2025-present loop3r