观前须知

笔者的博客主页

声明

本文使用 CC BY-NC-SA 4.0 许可。

本文为笔者在 OI 学习中的复习向学习笔记。
部分内容会比较简略服务器托管。
如有好的习题会不断补充。

知识简介

定义

基环树是一个有 (n) 个点 (n) 条边的连通图。
因为树有 (n) 个点 (n-1) 条边。
所以基环树可以看作是加了一条边的树。
那么也就是加了个环的树。
注意：题目中给 (n) 点 (n) 边时可能是基环树，也可能是基环树森林。
后一种情况分连通分量分别做即可。

如图：

拓扑排序找环

无向图：
不断地删除 1 度点，直到留下的全部都是 2 度点，即为环。

有向图：
同上，只不过每次删入度为 0 的点。

DFS找环

无向图：
走的时候记 dfn 和 fa，
遇到遍历过且 dfn 大的点（防止重复计算），
就不断跳 fa 并记录。

代码：

void Dfs(int u) {
    dfn[u] = ++Time;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa[u]) continue;
        if (!dfn[v]) { fa[v] = u, Dfs(v); }
        else {
            if (dfn[v] 

有向图：
如果边指向叶子可以反过来。
边指向根的树只需要不断向上跳 fa，同时打标记，
直到跳到树的根后，再跳到的点已经打过标记了，那么就找到环了。
（如果要树型DP的话可以再建个反向图，就不用建双向图了）

代码：

while (!vis[x]) vis[x] = true, x = fa[x];
int v = x;
while (v != x) loop[++cnt] = v = fa[v];

基环树常见问题处理方式

把环断开，发现图变成了若干个森林。
那么可以把基环树看作用一个环连接着的若干棵树。
这时候就可以先断环，然后再树型DP了。
特别地，有些题涉及到树之间经过环的转移。
这类问题可以分类讨论成不经过环的和经过环的分别处理。
由于有环的出现，破环为链也比较常用。

习题

Luogu P2607 【ZJOI2008】 骑士

首先这个东西显服务器托管然可以树型DP做。
但是这里是个基环树森林。
发现对于环的任意两个相邻点只能二选一或都不选。
那么任取环上的两个点分别做树型dp取 (max(f_{u_1,0},f_{u_2,0}))，然后对每个基环树求和即可。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 知乎：多云架构下大模型训练，如何保障存储稳定性

【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告” 知乎，中文互联网领域领先的问答社区和原创内容平台，2011 年 1 月正式上线，月活跃用户超过 1 亿。平台的搜索和推荐服务得益于先进的 AI 算法，数百名算法工程师基于数据平台和机…