如何使用不相交集检测无向图中的圈？

Question

算法：

For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
   Union(u, v)
else:
  return true // cycle detected
return false

图表：

(1)-------(2)

邻接列表：

[1] -

[2] -

不相交集：

{{1}, {2}}

迭代1：

边e=（1，2）

联盟（1,2）

不相交集={{1，2}}

迭代2：

边e=（2，1）

2和1都属于同一个集合，所以算法检测到一个循环，很明显图不包含循环。

对于有向图，该算法可以完美地工作。请帮我分析一下。

Answer 1

循环必须有明显的边！在联合查找算法中，迭代所有边。您需要从邻接列表中过滤出重复的边。在您的情况下，只有一次迭代，因此它将返回false。