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

Question

Alice and Bob have an undirected graph of n nodes and three types of edges:

• Type 1: Can be traversed by Alice only.
• Type 2: Can be traversed by Bob only.
• Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

Solution

对于A，B皆互通的边的权重比只对A或B连通的边的权重高。（多提供另一种联通）

因此先选择双连通的边，并加入两个并查集，由于选择了边，因此res–。

然后选择单连通的边，如果并查集中的两个节点并不互通，则选择这个边，并加入对应并查集。

每次连通两个节点，则集合数量减少1。

如果最终两个并查集的数量不是1，则并非所有节点都互相连通，返回-1。

否则返回未选择的边数res。

Code

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind ufA = new UnionFind(n), ufB = new UnionFind(n);
        int res = edges.length;

        for(int[] edge : edges){
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1; 
            if(type == 3 && !ufA.isConnected(u, v)){
                ufA.union(u, v);
                ufB.union(u, v);
                res--;
            }

        }

        for(int[] edge : edges){
            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1; 

            if(type == 1 && !ufA.isConnected(u, v)){
                ufA.union(u, v);
                res--;
            }
            else if(type == 2 && !ufB.isConnected(u, v)){
                ufB.union(u, v);
                res--;
            }
        }
        return ufA.sets == ufB.sets && ufA.sets == 1 ? res : -1;
    }
}

class UnionFind{
    int[] parent;
    int[] rank;
    public int sets;

    UnionFind(int n){
        parent = new int[n];
        rank = new int[n];
        sets = n;
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int i){
        if(parent[i] == i){
            return i;
        }
        return find(parent[i]);
    }

    public void union(int a, int b){
        int pa = find(a), pb = find(b);
        if(pa != pb) sets--;
        if(rank[pa] < rank[pb]){
            parent[pa] = pb;
        }
        else if(rank[pa] > rank[pb]){
            parent[pb] = pa;
        }
        else{
            parent[pa] = pb;
            rank[pb]++;
        }
    }

    public boolean isConnected(int a, int b){
        return find(a) == find(b);
    }
}