断边联合查找算法

Question

我需要一些帮助来解决联合查找问题。
这是问题。

There's an undirected connected graph with n nodes labeled 1..n. But some of the edges has been broken disconnecting the graph. Find the minimum cost to repair the edges so that all the nodes are once again accessible from each other.

Input:

n, an int representing the total number of nodes.
edges, a list of integer pair representing the nodes connected by an edge.
edgesToRepair, a list where each element is a triplet representing the pair of nodes between which an edge is currently broken and the cost of repearing that edge, respectively
(e.g. [1, 2, 12] means to repear an edge between nodes 1 and 2, the cost would be 12).

Example 1:
Input: n = 5, edges = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]],
edgesToRepair = [[1, 2, 12], [3, 4, 30], [1, 5, 8]]

Output: 20
There are 3 connected components due to broken edges: [1], [2, 3] and [4, 5]. We can connect these components into a single component by repearing the edges between nodes 1 and 2, and nodes 1 and 5 at a minimum cost 12 + 8 = 20.

public int minCostRepairEdges(int N, int[][] edges, int[][] edgesToRepair){

    int[] unionFind = new int[N+1];
    int totalEdges=0;
    for(int[] edge : edges){
        int ua = edge[0]; //node1
        int ub = edge[1]; //node2
        unionFind[ua] = ub;
        totalEdges++;
    }

    //change unionFind for some broken edge 
    for(int[] broken : edgesToRepair){
        int ua = Find(unionFind, broken[0]);
        int ub = Find(unionFind, broken[1]);
        if(ua == ub){
            unionFind[ua] = 0;
        }
    }

    Arrays.sort(edgesToRepair, (a,b)->(a[2]-b[2]));

    int cost=0;
    for(int[] i : edgesToRepair){
        int ua = Find(unionFind, i[0]);
        int ub = Find(unionFind, i[1]);

        if(ua != ub){
            unionFind[ua] = ub;
            cost += i[2];
            totalEdges++;
        }
    }
    return edgesToRepair==N-1 ? cost : -1;
}

public int find(int[] uf, int find){
    if(uf[find]==0) return find;
    uf[find] = find(uf, uf[find]);
    return uf[find];
}

以上是我目前的代码。

我的想法是
首先将所有边（给定 edges[][]）添加到 UnionFind，然后根据给定的 edgesToRepair 信息更新它。（如果边缘被破坏然后将在 union -find 中更新它）
然后尝试做基本的联合查找算法以最小的成本连接两个节点。

这里有什么错误的做法吗？
首先，当 unionFind 坏了时，我无法更新它。
我不知道如何处理两个节点之间的完整边缘。

任何建议都会有所帮助。

Answer 1

您应该使用 Kruskal 算法找到由现有边和损坏（修复）边组成的最小成本生成树：

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

只需考虑现有边缘的成本为 0，而损坏的边缘有其修复成本。

断边联合查找算法

broken edges union-find Algorithm

algorithm

union-find