Leetcode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

[Woodyiiiiiii]

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

从节点数量和边数量就可以知道，DFS和BFS用不了了，剩下的拓扑排序和并查集，也就只能从并查集入手了，因为只有它能保证O(nlgn)时间复杂度，只需要遍历边和连接边。

那么接下来是思考如何转换删除操作和选中边删除。这个删除操作在并查集里做不出来，并查集只能连接，并且，这个删除操作还只能在O(1)复杂度下。

同时观察到，边有三种类型和两个人，两种特定边并不与另一者相关，也就是说Alice的边跟Bob不相关，Bob的边跟Alice不相关。所以可以直接分别建立Alice和Bob的并查集结构。

然后是删除操作的解释。上面说了只能用O(1)，所以之前想的用dfs的类似选或不选的算法更是不可能。所以不妨直接鲁莽点，用计数法，假如两点不相连，则将有用的边数+1，否则删除的边数+1，最后判断有用的边数是否等于n-1即可，有些类似贪心的思想。

那么会不会出现边顺序影响结果的情况？比如先确立了某条边结果另一条边有影响？不会，我们只关注连通性。最后判断是否是n-1即可。

另外还有一个需要注意的地方。因为是要求最大删除边个数，所以需要从共有边开始判断连通性，因为这样才能贪心地最大化利用共有边的特性，这样到了遍历独特边的时候就可以更多地删除了。

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> b[0] - a[0]);
        UnionFind aliceUnion = new UnionFind(n);
        UnionFind bobUnion = new UnionFind(n);
        int rm = 0, ae = 0, be = 0;
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (aliceUnion.union(edge[1] - 1, edge[2] - 1)) {
                    rm++;
                } else {
                    ae++;
                }
            } else if (edge[0] == 2) {
                if (bobUnion.union(edge[1] - 1, edge[2] - 1)) {
                    rm++;
                } else {
                    be++;
                }
            } else {
                boolean check = true;
                if (!aliceUnion.union(edge[1] - 1, edge[2] - 1)) {
                    ae++;
                    check = false;
                }
                if (!bobUnion.union(edge[1] - 1, edge[2] - 1)) {
                    be++;
                    check = false;
                }
                if (check) {
                    rm++;
                }
            }
        }
        return ae == n - 1 && be == n - 1 ? rm : -1;
    }

    class UnionFind {
        int n;
        int[] f;
        int[] rank;

        public UnionFind(int n) {
            this.n = n;
            f = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                f[i] = i;
            }
        }

        public int find(int x) {
            if (f[x] == x) {
                return x;
            }
            f[x] = find(f[x]);
            return f[x];
        }

        public boolean union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx == fy) {
                return true;
            }
            if (rank[fx] < rank[fy]) {
                f[fx] = fy;
                rank[fy] += rank[fx];
            } else {
                f[fy] = fx;
                rank[fx] += rank[fy];
            }
            return false;
        }
    }
}