一、概念
基环树（Unicyclic Graph）是连通且恰好包含一个简单环的图结构，其本质是在树的基础上添加一条边（形成环），因此有n个顶点和n条边（n≥3）。基环树可分为两类：
无向基环树：由无向树添加一条边而成，环上任意两点间的路径不唯一（区别于树的唯一路径性质）。
有向基环树：分为内向基环树（每个节点出度为1，环外节点指向环内）和外向基环树（每个节点入度为1，环外节点背离环）。
基环树的核心特征是仅含一个简单环，这是其与树（无环）、仙人掌图（多环）的关键区别。
二、基环树的重点知识
1. 环的检测与定位
基环树问题的解决前提是找到环，常用方法包括：
DFS（深度优先搜索）：遍历图时记录访问状态，若遇到已访问且非父节点的节点，说明存在环（返祖边），沿父指针回溯即可得到环上所有节点。
拓扑排序：通过计算节点度数（无向图中），将度数为1的节点依次删除（类似剥洋葱），剩余度数≥2的节点即为环上节点（仅适用于无向基环树）。
2. 基环树的处理策略
基环树的问题（如动态规划、直径计算）需消除环的影响，常用方法有两种：
断环为树：断开环上任意一条边，将基环树转化为树，通过分类讨论处理环上节点的约束（如强制断开边的某一端点不选，再进行树形DP）。例如，“骑士”问题中，断开环上边后强制一端不选，分别计算两种情况的最大值。
环上DP：将环视为整体，先计算环上每个节点的子树贡献（如子树的最大深度、最大权值和），再将环“破环成链”（复制环序列），用动态规划处理环上的路径问题（如基环树的直径计算）。
3. 典型应用场景
基环树的典型问题包括：
最大权独立集（如“骑士”问题）：在基环树中选择若干节点，使得无相邻节点，且权值和最大。
基环树直径（如IOI2008“Island”问题）：求基环树中最长简单路径，需考虑路径是否经过环（不经过环则为子树直径，经过环则为环上路径加子树深度）。
环上节点的子树问题：如计算环上每个节点的子树大小、深度等，需先处理子树再合并环上的结果。
三、学习建议：
基环树的核心是处理环的约束，关键在于找到环并将其转化为树或链的问题。学习时需从基础概念入手，掌握环检测和处理的常用算法，通过专项练习提升解决问题的能力。推荐的练习顺序是：先练习环检测（如找环），再练习断环为树的DP（如“骑士”），最后挑战环上DP（如基环树直径）。