P3520 [POI2011] SMI-Garbage题解

· · 题解

题目大意

题目传送门

给我们一个无向图，需要找到所有的简单环。

思路

首先这些边中有许多边是没有用的，直接判断s==t就不要，否则就要这条边。

判断是否是NIE十分简单，看有没有点的度是奇数即可。

接着我们进行 dfs，将判断过的简单环上的点全部标记，之后可以用 vector 或栈存储答案都行。