基环树最大独立集

57 阅读 0 评论 38 点赞

我是靠谱客的博主眼睛大自行车，最近开发中收集的这篇文章主要介绍基环树最大独立集，觉得挺不错的，现在分享给大家，希望可以做个参考。

基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。显然，难度在于后者。

在基环树中，它可以选择叶子，并删除他们的邻接点并重复该过程，就可以直到剩下环。

解决这类问题一般都是去拆环，变一般树来处理。

题目：COCI2014/2015 Contest#1 D MAFIJA【基环树最大独立点集】 - Tieechal - 博客园 (cnblogs.com)

COCI2014/2015 Contest#1 D MAFIJA（树形DP/贪心）_Paulliant的博客-CSDN博客

最大独立集专题 - TieT - 博客园 (cnblogs.com)

找环可以用并查集来找，然后将它记录下来。
Q1:怎么断环？

利用并查集维护点与点的连通情况，把合并前就已经在同一集合的边记录下来。到时候dfs时，避开这条边即可。

Q2:断环后怎么搞？

断环后就形成了一棵普通的树，直接树形Dp即可（就是上面那道的做法）。但注意，我们记录的断掉的边(u,v)这两者不能同时取杀手。如何较方便的解决？直接分别以u,v为树根dfs两遍即可，最后将max(dp[u][0],dp[v][0])累计到答案（因为可能会有多个连通的块）。

整个算法的时间复杂度为O(N)。

以上就是眼睛大自行车为你收集整理的基环树最大独立集的全部内容，希望文章能够帮你解决基环树最大独立集所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

基环树 最大独立集