题解：CF962F Simple Cycles Edges

KidA · 2024-11-23 21:53:18 · 题解

对于有关环的无向图问题，自然往双连通方面思考。

容易发现一个点双连通分量（下文简称 V-DCC）中至多有一个简单环。

这是因为，若有多个简单环，则必定存在割点。

于是我们直接在每个 V-DCC 里边统计即可。

进一步可以发现，若一个 V-DCC 满足边数与点数相等，则它里面的所有边都是答案。

统计点数是简单的。如何统计边数？

类似于存储点的栈，我们也可以设置一个存储边的栈。

每次点与边分别弹出并统计各自数量即可。

代码实现，注意标注出来的细节点。