基环树

· · 个人记录

简介

严格来说，基环树并不能算是一种树。它是由一棵原本具有 n 个节点和 n\!-\!1 条边组成的树的基础上又添加了一条边得来的，因此会产生一个环，故得名「基环树」。因此，n 个点 n 条边的连通的无向图就是基环树；而对于有向图，同样是 n 个点，n 条边且每个点有且仅有一个入度（或出度）的有向连通图被称为内向树（或外向树），可以认为是有向的的基环树。尽管结构仍然不算很复杂，但相对树的问题，处理起来还是会麻（e）烦（xin）许多。

常见思路

  1. 【对于给定基环树】先找环，再处理环和森林

既然他和普通的「树」的区别在于这个多余的环，那么在很多时候我们可以直接考虑把这个环找出来（通常使用拓扑排序），然后原来的基环树就变成了一个环和若干个以环上节点为根的子树，分开处理即可。

  1. 【未给定基环树条件】根据已给条件构造

基环树真正的难点并不在于对于给定基环树的处理，而在于根据题目条件分析出基环树的性质。因此一定要注意观察分析题目中类似「每个点有且仅有一条出（入）边」的描述。

【例题】\scriptstyle\text{Island}\text{ / }\scriptstyle\text{星战}