专栏文章

qoj#1824. Special Cycle

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindeonn
此快照首次捕获于
2025/12/02 00:35
3 个月前
此快照最后确认于
2025/12/02 00:35
3 个月前
查看原文
Special Cycle
先考虑什么关键边可以删,当两个关键边共一个点时,答案中的环要么两条边都经过,要么两条边都不经过,所以可以合并成一条关键边。当有大于等于三个关键边共一个点时,环一定不会经过这个点,所以直接将这些关键边和点都删去。然后这张图一定没有关键边相邻。
如果一条边是割边,那它一定不会在答案里,所以可以直接删掉。如果这条割边是关键边,那两个端点也要删掉,避免答案经过这连个点。 这样一直删后,如果有一个大于1的连通块,则有解,否则无解。
对于每一个关键边都删去,如果删去无解,则保留在图上,如果删去有解,就删去,最后的连通块就是答案。
看不懂代码在写什么。

评论

0 条评论,欢迎与作者交流。

正在加载评论...