我们可以使用 Union-Find 数据结构检测有向图中的循环吗？
Can we detect cycles in directed graph using Union-Find data structure?
我知道可以使用 DFS 和 BFS 检测有向图中的环。我想知道我们是否可以使用 Union-Find 检测有向图中的循环？
- 如果是，那又如何呢？和
- 如果我们不能，那为什么？
不，我们不能使用 union-find 来检测有向图中的循环。这是因为有向图不能使用不相交集（执行联合查找的数据结构）来表示。
当我们说'a union b'时，我们无法确定边缘的方向
- a 要去 b 吗？ （或）
- b会去a吗？
但是，在无序图的情况下，每个连通分量相当于一个集合。所以union-find可以用来检测环路。每当您尝试对属于同一连通分量的两个顶点执行并集时，我们都可以说循环存在。
没有
举个例子：
- Q1。取一张无向图：
上面的无向图中有环吗？是的。我们可以使用 Union-Find 算法找到循环。
- Q2。现在看类似的有向图：
上面的有向图中有环吗？不！
但是如果你使用 Union-Find 算法来检测上面有向图中的循环，它会说是！由于 union-find 算法查看上图如下：
或
上图有循环吗？是的！但是原来的（Q2）问题被篡改了，这不是被问到的。所以 Union-find 算法会给出有向图的错误结果。
No, we cannot use union-find to detect cycles in a directed graph.
This is because a directed graph cannot be represented using the
disjoint-set(the data structure on which union-find is performed).
When we say 'a union b' we cannot make out the direction of edge
is a going to b? (or) is b going to a? But, incase of unordered
graphs, each connected component is equivalent to a set. So union-find
can be used to detect a cycle. Whenever you try to perform union on
two vertices belonging to the same connected component, we can say
that cycle exists.
只是想补充一下@Cherubim 的回答，我只是想到了这个问题，为什么我们不能弄清楚 'a union b' 的方向，就像我们可以认为它是连接到 b 一样（'a union b' 只有 a->b) 的节点?
那也会失败，考虑两个节点 x 和 y，它们连接 x -> y 并且它们在不相交的集合中已经有父节点，x_root 和 y_root。
那么当我们说 'x union y'（x 连接到 y）时会发生什么，我们使 y_root 成为 x_root 的父级。这告诉我们：
- x_root -> y_root（也可以相反）
- x_root 和 y_root 相连。 （他们可能会断开连接）
因此，除了方向不明确之外，主要问题还在于并非有向图中的每个节点都相互连接。
我知道可以使用 DFS 和 BFS 检测有向图中的环。我想知道我们是否可以使用 Union-Find 检测有向图中的循环？
- 如果是，那又如何呢？和
- 如果我们不能，那为什么？
不，我们不能使用 union-find 来检测有向图中的循环。这是因为有向图不能使用不相交集（执行联合查找的数据结构）来表示。
当我们说'a union b'时，我们无法确定边缘的方向
- a 要去 b 吗？ （或）
- b会去a吗？
但是，在无序图的情况下，每个连通分量相当于一个集合。所以union-find可以用来检测环路。每当您尝试对属于同一连通分量的两个顶点执行并集时，我们都可以说循环存在。
没有
举个例子：
- Q1。取一张无向图：
上面的无向图中有环吗？是的。我们可以使用 Union-Find 算法找到循环。
- Q2。现在看类似的有向图：
上面的有向图中有环吗？不！ 但是如果你使用 Union-Find 算法来检测上面有向图中的循环，它会说是！由于 union-find 算法查看上图如下：
上图有循环吗？是的！但是原来的（Q2）问题被篡改了，这不是被问到的。所以 Union-find 算法会给出有向图的错误结果。
No, we cannot use union-find to detect cycles in a directed graph. This is because a directed graph cannot be represented using the disjoint-set(the data structure on which union-find is performed).
When we say 'a union b' we cannot make out the direction of edge
is a going to b? (or) is b going to a? But, incase of unordered graphs, each connected component is equivalent to a set. So union-find can be used to detect a cycle. Whenever you try to perform union on two vertices belonging to the same connected component, we can say that cycle exists.
只是想补充一下@Cherubim 的回答，我只是想到了这个问题，为什么我们不能弄清楚 'a union b' 的方向，就像我们可以认为它是连接到 b 一样（'a union b' 只有 a->b) 的节点?
那也会失败，考虑两个节点 x 和 y，它们连接 x -> y 并且它们在不相交的集合中已经有父节点，x_root 和 y_root。 那么当我们说 'x union y'（x 连接到 y）时会发生什么，我们使 y_root 成为 x_root 的父级。这告诉我们：
- x_root -> y_root（也可以相反）
- x_root 和 y_root 相连。 （他们可能会断开连接）
因此，除了方向不明确之外，主要问题还在于并非有向图中的每个节点都相互连接。