1579. Remove Max Number of Edges to Keep Graph Fully Traversable
Posted Updated LeetCode / Hard / Review3 minutes read (About 493 words)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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);
    }
}
1697. Checking Existence of Edge Length Limited Paths
Posted Updated LeetCode / Hard / Review4 minutes read (About 579 words)

1697. Checking Existence of Edge Length Limited Paths

Question

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

Read more
Follow

Recents

Archives

Links

×