algorithm - 如何使用不相交集检测无向图中的循环？

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]

[2] -> [1]

不相交集：

{{1}、{2}}

迭代 1：

边 e = (1, 2)

联合(1, 2)

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

迭代 2：

边 e = (2, 1)

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

该算法完美地适用于有向图。请帮我分析一下。

Answer 1

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