LeetCode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable

LeetCode Problem 1579

Difficulty: 🔴 Hard
Topics: Union-Find, Graph Theory

Solution

Problem Understanding

The problem presents an undirected graph with n nodes and three types of edges: Type 1 for Alice, Type 2 for Bob, and Type 3 for both Alice and Bob. The input edges is an array where each element [type, u, v] represents a bidirectional edge connecting nodes u and v of the specified type. The goal is to determine the maximum number of edges that can be removed while still allowing both Alice and Bob to traverse the entire graph. If it is impossible for either Alice or Bob to traverse all nodes, we must return -1.

In simpler terms, we need to maintain connectivity for both Alice and Bob simultaneously, and edges that do not contribute to this connectivity can be removed. Since Alice and Bob share Type 3 edges, these edges are the most valuable because they count toward connectivity for both. Type 1 and Type 2 edges are only useful to their respective users. The constraints, with n up to 10^5 and edges up to 3 * n * (n - 1) / 2, indicate that brute-force solutions are infeasible and that an efficient Union-Find (Disjoint Set Union) approach is appropriate.

Important edge cases include graphs where connectivity is impossible without all edges, graphs where all edges are Type 3, and disconnected components for one user but not the other.

Approaches

Brute Force Approach: One could attempt to remove each edge one by one and check if the resulting graph is still fully traversable by both Alice and Bob using BFS or DFS. This approach is correct but extremely inefficient. For each edge removal, checking connectivity is O(n + m), leading to overall complexity of O(m*(n+m)), which is not feasible for the upper constraints.

Optimal Approach: The key insight is to use Union-Find to track connectivity. We process Type 3 edges first, because they contribute to both Alice and Bob's connectivity. Then we process Type 1 edges for Alice and Type 2 edges for Bob separately. If an edge connects nodes already in the same connected component, it is redundant and can be removed. After processing all edges, we check if Alice and Bob are each connected (i.e., their respective Union-Find structures have only one component). If so, the count of redundant edges gives the maximum number we can remove. Otherwise, return -1.

Here, α(n) is the inverse Ackermann function, which is nearly constant for all practical purposes.

Algorithm Walkthrough

1. Initialize two Union-Find structures, one for Alice and one for Bob, each containing n nodes.
2. Sort or separate edges into Type 3, Type 1, and Type 2 lists.
3. Initialize a counter removed = 0 for redundant edges.
4. Process Type 3 edges first: For each edge (u, v), if u and v are already connected in Alice's Union-Find (and Bob's, since Type 3 affects both), increment removed. Otherwise, union u and v in both Alice's and Bob's Union-Find.
5. Process Type 1 edges for Alice: If u and v are already connected in Alice's Union-Find, increment removed. Otherwise, union them.
6. Process Type 2 edges for Bob: Similarly, union if disconnected, otherwise increment removed.
7. After processing all edges, check if both Alice's and Bob's Union-Find structures have exactly one connected component. If not, return -1.
8. Return the value of removed.

Why it works: By prioritizing Type 3 edges, we maximize shared connectivity and minimize the need for separate Type 1 or Type 2 edges. Redundant edges do not contribute to connectivity and can safely be removed. Union-Find guarantees correct tracking of connected components efficiently.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        self.components = n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1
        self.components -= 1
        return True

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        alice_uf = UnionFind(n)
        bob_uf = UnionFind(n)
        removed = 0
        
        # Process Type 3 edges first
        for t, u, v in edges:
            if t == 3:
                if not alice_uf.union(u, v):
                    removed += 1
                else:
                    bob_uf.union(u, v)
        
        # Process Type 1 edges for Alice
        for t, u, v in edges:
            if t == 1:
                if not alice_uf.union(u, v):
                    removed += 1
        
        # Process Type 2 edges for Bob
        for t, u, v in edges:
            if t == 2:
                if not bob_uf.union(u, v):
                    removed += 1
        
        if alice_uf.components != 1 or bob_uf.components != 1:
            return -1
        return removed

Explanation: We maintain separate Union-Find structures for Alice and Bob. Type 3 edges are applied to both. Union operations return False if the nodes are already connected, allowing us to count redundant edges. After all edges are processed, we confirm that each graph is fully connected.

Go Solution

package main

type UnionFind struct {
	parent     []int
	rank       []int
	components int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n+1)
	rank := make([]int, n+1)
	for i := 0; i <= n; i++ {
		parent[i] = i
	}
	return &UnionFind{parent, rank, n}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
	xr, yr := uf.Find(x), uf.Find(y)
	if xr == yr {
		return false
	}
	if uf.rank[xr] < uf.rank[yr] {
		uf.parent[xr] = yr
	} else if uf.rank[xr] > uf.rank[yr] {
		uf.parent[yr] = xr
	} else {
		uf.parent[yr] = xr
		uf.rank[xr]++
	}
	uf.components--
	return true
}

func maxNumEdgesToRemove(n int, edges [][]int) int {
	aliceUF := NewUnionFind(n)
	bobUF := NewUnionFind(n)
	removed := 0

	for _, edge := range edges {
		if edge[0] == 3 {
			if !aliceUF.Union(edge[1], edge[2]) {
				removed++
			} else {
				bobUF.Union(edge[1], edge[2])
			}
		}
	}

	for _, edge := range edges {
		if edge[0] == 1 {
			if !aliceUF.Union(edge[1], edge[2]) {
				removed++
			}
		} else if edge[0] == 2 {
			if !bobUF.Union(edge[1], edge[2]) {
				removed++
			}
		}
	}

	if aliceUF.components != 1 || bobUF.components != 1 {
		return -1
	}
	return removed
}

Go-specific notes: We define a UnionFind struct and constructor NewUnionFind. Slices handle the parent and rank arrays. Union returns a boolean indicating redundancy. Edge indices are accessed using edge[1] and edge[2], consistent with 1-based node indexing.

Worked Examples

Example 1: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]