本蒟蒻在做题的时候,经常会出现点双题用边双,边双题用点双等情况。
但是题解很少会讲为什么用点双/边双,而不是另一种。
例如下面这道题:
给定无向连通图,求所有在且仅在 1 个简单环中的边。
我的想法是把所有边双找出来,看边数是否等于点数。
但会出现反例:
正解是把所有点双找出来。
bdfs 发现大多数 blog 没有提及,小部分说的也比较模糊,例如“点双的限制比边双严格”,“点双一定是边双,边双是若干个点双拼起来”。
故求问:
- 有没有一些题目的普遍特点/条件,提示使用点双/边双?
- 有没有一些好的方法,能够判断使用点双/边双?
- 广义地,点双和边双在应用中,有什么区别?