kruscal用数组代替并查集可以吗？

Question

用一个bool join［max_n］数组保存点是否已经有边连接，在遍历边时，如果边两端的点x和y的join［x］和join［y］都等于1，则说明这两个点都有边连接他们了，则不考虑这条边。这样可以吗？

Answer 1

两个节点 join 为 1 并不能说明两个点在同一个联通块的。也就是说可能两个点在不同联通块内而都有别边连接，那么这条边会合并两个联通块。所以还是并查集吧。
当然有一种叫做 link-cut-tree 的数据结构也可以轻松维护最小生成树，本质也是维护联通块的连通性。

Answer 2

kruscal算法在求最小生成树时，充分利用了贪心的特点。比如:

AB和CD会最先被选出来，此时它们被访问过了，但不属于同一棵树。如果ABCD不联通，此时算法已经结束，求出了这个森林的所有最小生成树，但使用数组并不知道这些点是属于一棵树还是分别属于多棵树。