上岸 I LeetCode Weekly Contest 194解題報告

class Edge {
    int id, a, b, v;

    public Edge(int id, int a, int b, int v) {
        this.id = id;
        this.a = a;
        this.b = b;
        this.v = v;
    }
}

class UnionFind {
    int[] fa;

    public UnionFind(int n) {
        fa = new int[n];
        Arrays.fill(fa, -1);
    }

    public int find(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = find(fa[x]);
    }

    public void merge(int a, int b) {
        int Fa = find(a);
        int Fb = find(b);
        fa[Fa] = Fb;
    }
}

class Solution {

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        List<Edge> edgeList = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            int[] e = edges[i];
            edgeList.add(new Edge(i, e[0], e[1], e[2]));
        }
        edgeList.sort((a, b)->a.v-b.v);
        int mst = calcMST(n, edgeList, -1, -1); // 真正的最小生成樹
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        res.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            int t1 = calcMST(n, edgeList, i, -1); // 不使用 i 構造最小生成樹
            int t2 = calcMST(n, edgeList, -1, i); // 必使用 i 構造最小生成樹
            if (t1 != mst) { // 不使用, MST變大, 關鍵邊
                res.get(0).add(i);
            } else if (t2 == mst) { // 使用, MST不變, 且不是關鍵邊, 則是偽關鍵邊
                res.get(1).add(i);
            }
        }
        return res;
    }

    private int calcMST(int n, List<Edge> edgeList, int forbidden, int must) {
        // 不使用 forbidden, 而必須使用 must 構造最小生成樹
        UnionFind uf = new UnionFind(n);
        int res = 0;
        int cnt = 0;
        if (must >= 0) {
            cnt++;
            for (var e : edgeList) {
                if (e.id == must) {
                    res += e.v;
                    uf.merge(e.a, e.b);
                    break;
                }
            }
        }
        for (var e : edgeList) {
            if (e.id == forbidden || e.id == must) {
                continue;
            }
            int fa = uf.find(e.a);
            int fb = uf.find(e.b);
            if (fa != fb) {
                uf.merge(fa, fb);
                cnt++;
                res += e.v;

            }
            if (cnt == n - 1) return res;
        }
        return 0x3f3f3f3f;
    }
}