令 G = (V, E) 为加权、连通且无向图，令 e 为 E 中的任意边。展示一个线性时间算法，该算法决定是否存在包含边 e 的最小生成树。
我设法为问题 1 找到了一个奇怪的“解决方案”，它似乎有效，但我认为它不是线性的：
他们建议对每条边 (u,v) 使用 union find 并执行 Union(u,v)，使得 W(u,v) < W(e)。现在，假设 e = (x,y)。现在如果 find(x) != find(y) 那么 x 和 y 没有连接，W(e) 肯定是 Kruskal 算法检查的下一个权重，所以肯定存在一个包含边缘的 MST e.
另一方面，如果 find(x) = find(y) 那么如果我们将 Kruskal 算法运行到这一点，x 和 y 肯定会连接，所以我们不能将边 e 添加到任何 MST（通过操纵具有相同权重的边的排序顺序 - Kruskal 算法可用于创建任何 MST）。
我不明白为什么这是线性的？由于工会，它不应该花费 O( |E| alpha(|V|) ) 吗？
也许还有另一种方法可以在线性时间内做到这一点？
提前致谢