专栏文章
题解:CF962F Simple Cycles Edges
CF962F题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mir0txh4
- 此快照首次捕获于
- 2025/12/04 13:54 3 个月前
- 此快照最后确认于
- 2025/12/04 13:54 3 个月前
对于有关环的无向图问题,自然往双连通方面思考。
容易发现一个点双连通分量(下文简称 V-DCC)中至多有一个简单环。
这是因为,若有多个简单环,则必定存在割点。
于是我们直接在每个 V-DCC 里边统计即可。
进一步可以发现,若一个 V-DCC 满足边数与点数相等,则它里面的所有边都是答案。
统计点数是简单的。如何统计边数?
类似于存储点的栈,我们也可以设置一个存储边的栈。
每次点与边分别弹出并统计各自数量即可。
代码实现,注意标注出来的细节点。
相关推荐
评论
共 1 条评论,欢迎与作者交流。
正在加载评论...