To do list #2 : ZHQOI R1

· · 个人记录

删边

找两个相连的点,保留它们之间的边,然后把这两个点到外面的所有边都断掉。但这样会产生一些孤立点,所以孤立点的边不需要断掉。

如果到最后发现有边被断掉了,那就划分成功了。否则失败了。但失败了不一定代表无解,只说明这两个点最终一定不在同一个连通块中。

找一个度数最小的点,枚举这个点的所有出边保留下来,如果枚举到任意一条边保留下来之后有解那么直接输出即可,如果枚举全部失败说明这个点不和任意一个相邻的点处在同一个连通块中,那么一定会出现孤立点,无解。