我们可以使用Union-Find数据结构来检测有向图中的圈吗？

Question

我知道可以使用DFS和BFS来检测有向图中的圈。我想知道我们是否可以用以下方法检测有向图中的圈

联合查找

还是不想？

如果是，那是怎么做的？和

如果我们不能，那为什么呢？

Answer 1

不，我们不能使用联合查找来检测有向图中的循环。这是因为不能使用不相交集合(执行联合查找的数据结构)来表示有向图。

当我们说'a并集b‘时，我们看不出边的方向。

A是去b的吗？(或)

B去a吗？

但是，在无序图的情况下，每个连通分支等价于一个集合。因此，联合查找可用于检测循环。每当您尝试对属于同一连通分量的两个顶点执行并集时，我们都可以说存在循环。