Remove Max Number of Edges to Keep Graph Fully Traversable

Hard
1548.

Remove Max Number of Edges to Keep Graph Fully Traversable

Remove Max Number of Edges to Keep Graph Fully Traversable is a hard coding problem on greedy, graph and union find, asked in Amazon and Google interviews.

Alice and Bob share an undirected graph of n nodes numbered 1 to n. Each edges[i] = [typei, ui, vi] is an edge between ui and vi of one of three types:

  • type 1: only Alice can use it,
  • type 2: only Bob can use it,
  • type 3: both can use it.

The graph is fully traversable for a person if, using only the edges they may use, they can get from any node to any other node.

Return the maximum number of edges you can remove so that the graph stays fully traversable for both Alice and Bob, or -1 if it is not fully traversable for both to begin with.

Example 1

Input
n = 3, edges = [[3,1,2],[1,2,3],[2,2,3],[1,1,3],[3,2,3]]
Output
3
Explanation
The two shared edges `[3,1,2]` and `[3,2,3]` already connect everything for both; the other three can go.

Example 2

Input
n = 4, edges = [[3,1,2],[1,2,3],[2,3,4],[1,3,4],[2,2,3]]
Output
0

Example 3

Input
n = 3, edges = [[1,1,2],[2,2,3],[3,1,2]]
Output
-1
Explanation
Alice can never reach node 3.

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2)
  • edges[i].length == 3
  • 1 <= typei <= 3
  • 1 <= ui < vi <= n
  • all tuples (typei, ui, vi) are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var maxNumEdgesToRemove = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Max Number of Edges to Keep Graph Fully Traversable Solution

Remove Max Number of Edges to Keep Graph Fully Traversable solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove Max Number of Edges to Keep Graph Fully Traversable is a hard coding problem on greedy, graph and union find, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Greedy, Graph, Union Find
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Alice and Bob share an undirected graph of n nodes numbered 1 to n. Each edges[i] = [typei, ui, vi] is an edge between ui and vi of one of three types:

  • type 1: only Alice can use it,
  • type 2: only Bob can use it,
  • type 3: both can use it.

The graph is fully traversable for a person if, using only the edges they may use, they can get from any node to any other node.

Return the maximum number of edges you can remove so that the graph stays fully traversable for both Alice and Bob, or -1 if it is not fully traversable for both to begin with.

Example 1

Input: n = 3, edges = [[3,1,2],[1,2,3],[2,2,3],[1,1,3],[3,2,3]]
Output: 3
Explanation: The two shared edges `[3,1,2]` and `[3,2,3]` already connect everything for both; the other three can go.

Example 2

Input: n = 4, edges = [[3,1,2],[1,2,3],[2,3,4],[1,3,4],[2,2,3]]
Output: 0

Example 3

Input: n = 3, edges = [[1,1,2],[2,2,3],[3,1,2]]
Output: -1
Explanation: Alice can never reach node 3.

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2)
  • edges[i].length == 3
  • 1 <= typei <= 3
  • 1 <= ui < vi <= n
  • all tuples (typei, ui, vi) are distinct

Hints for Remove Max Number of Edges to Keep Graph Fully Traversable

  1. Hint 1

    Count the edges you must keep instead of the ones you remove: the answer is edges.length minus the fewest edges that keep both people connected.

  2. Hint 2

    A shared (type 3) edge does the work of two private edges, so it should be preferred whenever it joins two separate pieces.

  3. Hint 3

    Keep two union-finds. Add type-3 edges first to both, then type-1 edges to Alice's and type-2 edges to Bob's, counting only the edges that actually merge two sets. If either structure is still split, return -1.

How to solve Remove Max Number of Edges to Keep Graph Fully Traversable

Greedy union-find: take shared edges first (each can serve both people), then private edges only where still needed; every edge that merges nothing is removable.

Approach

  1. Create union-finds for Alice and Bob over nodes 1..n.
  2. For each type-3 edge, union it in both structures if it merges two of Alice's sets (Bob's structure is identical at this point); count it as kept.
  3. For each type-1 edge, union it in Alice's structure, counting it if it merges; likewise type-2 edges in Bob's structure.
  4. If either structure has more than one component, return -1; otherwise return edges.length − kept.

Why it works

Each person needs a spanning forest of exactly n − 1 edges. Let s be the number of shared edges used; then the kept total is s + (n − 1 − s) + (n − 1 − s) = 2(n − 1) − s, so maximising s is the whole game. Adding all useful type-3 edges first yields a spanning forest of the type-3 subgraph, which has the maximum possible number of shared edges; the private edges then complete each person's tree independently, using the minimum number for each.

Complexity

  • Time — O(m · α(n))
  • Space — O(n)

Pitfalls

  • Processing edges in input order instead of type 3 first can waste private edges where a shared edge would have done.
  • A type-3 edge that merges nothing for Alice also merges nothing for Bob — they share the same history at that stage.
  • Check both people's connectivity at the end; either one failing means -1.

Reference solution

Python

from typing import List

def maxNumEdgesToRemove(n: int, edges: List[List[int]]) -> int:
    alice = list(range(n + 1))
    bob = list(range(n + 1))

    def find(root, x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(root, a, b):
        ra, rb = find(root, a), find(root, b)
        if ra == rb:
            return False
        root[ra] = rb
        return True

    used = 0
    comps_a = comps_b = n
    for t, u, v in edges:
        if t == 3 and union(alice, u, v):
            union(bob, u, v)
            used += 1
            comps_a -= 1
            comps_b -= 1
    for t, u, v in edges:
        if t == 1 and union(alice, u, v):
            used += 1
            comps_a -= 1
        elif t == 2 and union(bob, u, v):
            used += 1
            comps_b -= 1
    if comps_a != 1 or comps_b != 1:
        return -1
    return len(edges) - used

Java

public static int maxNumEdgesToRemove(int n, int[][] edges) {
    int[] alice = new int[n + 1], bob = new int[n + 1];
    for (int i = 0; i <= n; i++) { alice[i] = i; bob[i] = i; }
    int used = 0, compsA = n, compsB = n;
    for (int[] e : edges) {
        if (e[0] == 3 && rmUnion(alice, e[1], e[2])) { rmUnion(bob, e[1], e[2]); used++; compsA--; compsB--; }
    }
    for (int[] e : edges) {
        if (e[0] == 1 && rmUnion(alice, e[1], e[2])) { used++; compsA--; }
        else if (e[0] == 2 && rmUnion(bob, e[1], e[2])) { used++; compsB--; }
    }
    if (compsA != 1 || compsB != 1) return -1;
    return edges.length - used;
}

static int rmFind(int[] root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

static boolean rmUnion(int[] root, int a, int b) {
    int ra = rmFind(root, a), rb = rmFind(root, b);
    if (ra == rb) return false;
    root[ra] = rb;
    return true;
}

C++

static int rmFind(vector<int>& root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

static bool rmUnion(vector<int>& root, int a, int b) {
    int ra = rmFind(root, a), rb = rmFind(root, b);
    if (ra == rb) return false;
    root[ra] = rb;
    return true;
}

int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
    vector<int> alice(n + 1), bob(n + 1);
    for (int i = 0; i <= n; i++) { alice[i] = i; bob[i] = i; }
    int used = 0, compsA = n, compsB = n;
    for (auto& e : edges) {
        if (e[0] == 3 && rmUnion(alice, e[1], e[2])) { rmUnion(bob, e[1], e[2]); used++; compsA--; compsB--; }
    }
    for (auto& e : edges) {
        if (e[0] == 1 && rmUnion(alice, e[1], e[2])) { used++; compsA--; }
        else if (e[0] == 2 && rmUnion(bob, e[1], e[2])) { used++; compsB--; }
    }
    if (compsA != 1 || compsB != 1) return -1;
    return (int)edges.size() - used;
}

JavaScript

var maxNumEdgesToRemove = function(n, edges) {
    var alice = [], bob = [];
    for (var i = 0; i <= n; i++) { alice.push(i); bob.push(i); }
    var find = function(root, x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    var union = function(root, a, b) {
        var ra = find(root, a), rb = find(root, b);
        if (ra === rb) return false;
        root[ra] = rb;
        return true;
    };
    var used = 0, compsA = n, compsB = n;
    for (var k = 0; k < edges.length; k++) {
        var e = edges[k];
        if (e[0] === 3 && union(alice, e[1], e[2])) { union(bob, e[1], e[2]); used++; compsA--; compsB--; }
    }
    for (var j = 0; j < edges.length; j++) {
        var f = edges[j];
        if (f[0] === 1 && union(alice, f[1], f[2])) { used++; compsA--; }
        else if (f[0] === 2 && union(bob, f[1], f[2])) { used++; compsB--; }
    }
    if (compsA !== 1 || compsB !== 1) return -1;
    return edges.length - used;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 264 greedy problems · the whole catalogue

Learn the technique: Greedy Algorithms · Graph Data Structure