qoj#1824. Special Cycle

· · 个人记录

Special Cycle

先考虑什么关键边可以删,当两个关键边共一个点时,答案中的环要么两条边都经过,要么两条边都不经过,所以可以合并成一条关键边。当有大于等于三个关键边共一个点时,环一定不会经过这个点,所以直接将这些关键边和点都删去。然后这张图一定没有关键边相邻。

如果一条边是割边,那它一定不会在答案里,所以可以直接删掉。如果这条割边是关键边,那两个端点也要删掉,避免答案经过这连个点。 这样一直删后,如果有一个大于1的连通块,则有解,否则无解。

对于每一个关键边都删去,如果删去无解,则保留在图上,如果删去有解,就删去,最后的连通块就是答案。

看不懂代码在写什么。