两个不相交集之间的路径（路径算法）
path between two disjoint sets (path algorithm)
我有以下问题。我在图中有两组不相交的顶点，我想知道这两组之间是否存在路径。
我只需要知道有这样一条路径就可以了
我在某处读到这可以使用 union-find 数据结构来解决，但我找不到适合我需要的算法
非常感谢任何帮助。
可以有效解决问题
用A和B表示两组顶点，并初始化一个联合查找数据结构，使得图的每个顶点v属于它自己的集合。
设a1为A的任意顶点。对 A 中的每个顶点 a 执行 UNION(FIND(a1), FIND(a))（除 a1 之外的所有顶点都将成为集合的代表）。然后对B中的顶点做同样的事情：设b1为B的任意一个顶点，对[=11=的每个顶点b执行UNION(FIND(b1), FIND(b)) ].
现在 FIND(a1) returns 恰好属于 A 的顶点集和 FIND(b1) returns 恰好属于 B 的顶点集.特别是，如果 A 和 B 彼此相交，则 FIND(a1)=FIND(b1)。对于图中的每条边 (u,v)，执行 UNION(FIND(u), FIND(v)).
当且仅当您在上述过程中将 a1 集合与 b1 集合合并时，A 和 B 之间存在一条路径。
您完成的操作次数最多 UNION/FIND 次 O(|E|+|A|+|B|)。因此，算法的 运行 时间是 O(alpha(n)*(|E|+|A|+|B|))，其中 alpha(n) 是 Inverse Ackerman function。逆阿克曼函数，增长非常缓慢，是每个 UNION 或 FIND 操作的 运行 时间的上限。
我有以下问题。我在图中有两组不相交的顶点，我想知道这两组之间是否存在路径。
我只需要知道有这样一条路径就可以了
我在某处读到这可以使用 union-find 数据结构来解决，但我找不到适合我需要的算法
非常感谢任何帮助。
用A和B表示两组顶点，并初始化一个联合查找数据结构，使得图的每个顶点v属于它自己的集合。
设a1为A的任意顶点。对 A 中的每个顶点 a 执行 UNION(FIND(a1), FIND(a))（除 a1 之外的所有顶点都将成为集合的代表）。然后对B中的顶点做同样的事情：设b1为B的任意一个顶点，对[=11=的每个顶点b执行UNION(FIND(b1), FIND(b)) ].
现在 FIND(a1) returns 恰好属于 A 的顶点集和 FIND(b1) returns 恰好属于 B 的顶点集.特别是，如果 A 和 B 彼此相交，则 FIND(a1)=FIND(b1)。对于图中的每条边 (u,v)，执行 UNION(FIND(u), FIND(v)).
当且仅当您在上述过程中将 a1 集合与 b1 集合合并时，A 和 B 之间存在一条路径。
您完成的操作次数最多 UNION/FIND 次 O(|E|+|A|+|B|)。因此，算法的 运行 时间是 O(alpha(n)*(|E|+|A|+|B|))，其中 alpha(n) 是 Inverse Ackerman function。逆阿克曼函数，增长非常缓慢，是每个 UNION 或 FIND 操作的 运行 时间的上限。