边权取模的最小生成树

边权取模的最小生成树是指在一个带权无向图中，将每条边的权值取模后，得到的新图的最小生成树。这个问题可以使用Kruskal算法或Prim算法来解决。

Kruskal算法的实现步骤如下：
1. 将所有边按照权值从小到大排序。
2. 依次遍历每条边，如果该边的两个端点不在同一个连通块中，则将该边加入最小生成树中，并将这两个端点所在的连通块合并。
3. 直到最小生成树中有n-1条边为止，其中n为图中节点的个数。

代码实现如下（假设边的权值存储在一个二元组中，即(边的权值, 起点, 终点)）：

def kruskal(n, edges):
    # 初始化并查集
    parent = list(range(n))
    rank = [0] * n

    # 定义并查集的查找函数
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # 定义并查集的合并函数
    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return False
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
        return True

    # 将边按照权值从小到大排序
    edges.sort()

    # 遍历每条边，将其加入最小生成树中
    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((w, u, v))
            if len(mst) == n - 1:
                break

    return mst

Prim算法的实现步骤如下：
1. 选择一个起点，将其加入最小生成树中。
2. 从与最小生成树相邻的边中，选择一条权值最小的边，将其加入最小生成树中，并将该边的另一个端点加入最小生成树中。
3. 重复步骤2，直到最小生成树中有n-1条边为止，其中n为图中节点的个数。

代码实现如下（假设边的权值存储在一个字典中，即{(起点, 终点): 权值}）：

def prim(n, edges):
    # 初始化最小生成树和已经加入最小生成树的节点集合
    mst = []
    visited = set()

    # 选择一个起点
    start = next(iter(edges.keys()))

    # 将起点加入最小生成树和已经加入最小生成树的节点集合
    mst.append(start)
    visited.add(start[0])
    visited.add(start[1])

    # 重复选择权值最小的边，并将其加入最小生成树中
    while len(mst) < n - 1:
        min_edge = None
        min_weight = float('inf')
        for u, v in mst:
            for w, x in edges:
                if u == x and v != w and (w, v) not in mst and edges[(w, x)] < min_weight:
                    min_edge = (w, v)
                    min_weight = edges[(w, x)]
                elif v == x and u != w and (w, u) not in mst and edges[(w, x)] < min_weight:
                    min_edge = (w, u)
                    min_weight = edges[(w, x)]
        mst.append(min_edge)
        visited.add(min_edge[0])
        visited.add(min_edge[1])

    return mst