通常的想法是：如果图是一棵树，那么通过对顶点进行双色染色，并从更频繁的颜色中选取顶点，就可以轻松找到大小为 \(\lceil\frac{n}{2}\rceil\) 的独立集合。否则，图就是循环的。让我们得到一个没有任何边 “穿过 ”的循环。换句话说，它没有任何一对不相邻的顶点由边连接。如果它的长度最多为 \(k\)，则打印出来。否则，取其他每一个顶点（取一个顶点，留下一个顶点），最后就会得到一个足够大的独立集合。如何找到这样的循环？
第一个解决方案
让我们在图中做一个 DFS。当我们第一次碰到一个有后缘的节点时，我们取一条通向最深节点的后缘来结束循环。这个循环不可能有任何边穿过，因为我们节点的祖先都没有背边（根据定义）。
代码链接： https://pastebin.com/wsCXuzGy
第二种解决方案
让我们获取图中的任意一个循环。现在，让我们遍历不属于循环的边。每当遇到 “与循环交叉 ”的边，我们就用它将循环切割成两个长度较小的循环，并保留其中任何一个。最后，我们就得到了想要的循环。
代码链接： https://pastebin.com/ezwEURKW
通过www.DeepL.com/Translator（免费版）翻译
标签：1364D,一个,CodeForces,节点,循环,顶点,com,我们 From： https://www.cnblogs.com/gutongxing/p/18470992