写非割边优先代码

非割边优先算法是最小生成树算法的一种，可以用来求解带权无向图的最小生成树。其基本思想是：按边权从小到大的顺序依次考虑每条边，如果这条边不在当前生成树中，那么就加入生成树，否则就不加入。

下面是非割边优先算法的伪代码实现：

NonCutEdgeMST(G):
    sort edges of G in non-decreasing order of weight
    for each edge (u, v) in sorted edges:
        if there is a path from u to v in the current tree:
            continue
        otherwise:
            add (u, v) to the current tree
    return the current tree

其中，`G` 是带权无向图，`edges` 是图 `G` 的所有边，按照边权从小到大排序。

这里的关键是如何判断一条边是否在当前生成树中。可以使用深度优先搜索或广度优先搜索来找到从 `u` 到 `v` 的路径，如果存在路径，则说明 `(u, v)` 在当前生成树中，否则不在。如果使用深度优先搜索，时间复杂度为 $O(|E| + |V|)$，其中 $|E|$ 和 $|V|$ 分别为边数和顶点数。如果使用并查集进行优化，则时间复杂度可以达到 $O(|E|\log|V|)$。

下面是使用并查集进行优化的非割边优先算法的 Python 代码实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def non_cut_edge_mst(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    mst = []
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst

其中，`n` 是顶点数，`edges` 是边集，每条边表示为 `(u, v, w)`，其中 `u` 和 `v` 是边的两个端点，`w` 是边的权重。返回值为最小生成树的边集。