威风镰鼬

分类

题解(153)

/ 注册

全部文章（共2篇）

题解 | #Graph Coloring I#

思路无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所...

搜索二分图 tarjan

2021-08-26

3 567

题解 | #间谍网络#

思路这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。但是题目不保证是有向无环图，因此我们需要对环进...

tarjan 图论缩点强连通分量

2021-08-13

1 0