Remove Max Number of Edges to Keep Graph Fully Traversable solution and explanation
Google
9 more videos on this problem
Remove Max Number Of Edges To Keep Graph Fully Traversable | Leetcode - 1579 | DSU | GOOGLE | LivecodestorywithMIK · 27:54 · 14K views
Remove Max Number of Edges to Keep Graph Fully Traversable - Leetcode 1579 - PythonNeetCodeIO · 17:20 · 14K views
1579. Remove Max Number of Edges to Keep Graph Fully Traversable || Union Find || DSU || GraphAryan Mittal · 22:18 · 7K views
✅ Remove Max Number of Edges to Keep Graph Fully Traversable - LeetCode 1579 - Union FindLeet Logics · 7:31 · 1K views
LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully TraversableHappy Coding · 27:17 · 872 views
1579. Remove Max Number of Edges to Keep Graph Fully Traversable | DSU | LeetCode Daily ChallengeDeep Tech · 17:57 · 819 views
1579. Remove Max Number of Edges to Keep Graph Fully Traversable | Leetcode weekly contest 205 | DSUCP Addict · 10:15 · 608 views
1579. Remove Max Number of Edges to Keep Graph Fully Traversable (Leetcode Hard)Programming Live with Larry · 18:47 · 480 views
Daily Leetcode #1125: Apr 30, 2023 - 1579. Remove Max Number of Edges to Keep Graph Fully Traversa..Programming Live with Larry · 15:02 · 297 views
LeetCode Solutions 1579. Remove Max Number of Edges to Keep Graph Fully TraversableAbrar Sher · 15:51 · 233 views
The problem
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.
Example 1:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] Output: 2 Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.
Example 2:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] Output: 0 Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.
Example 3:
Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] Output: -1 Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.
Constraints:
1 <= n <= 1051 <= edges.length <= min(105, 3 * n * (n - 1) / 2)edges[i].length == 31 <= typei <= 31 <= ui < vi <= n- All tuples
(typei, ui, vi)are distinct.
Approach overview
Problem Overview: You are given a graph where edges can be used by Alice, Bob, or both. The goal is to remove the maximum number of edges while ensuring both Alice and Bob can still traverse the entire graph. If either cannot reach all nodes, return -1.
Approach 1: Edge Removal with Connectivity Check (DFS/BFS) (Time: O(E * (V + E)), Space: O(V))
Start with the full graph and attempt removing each edge one by one. After removing an edge, run a connectivity check for Alice and Bob separately using DFS or BFS. If both graphs remain fully connected, the edge is unnecessary and can stay removed; otherwise restore it. This brute-force method works conceptually but is extremely expensive because each removal requires a full traversal of the graph. It demonstrates the problem constraint: connectivity must be preserved for two different users.
Approach 2: Union-Find with Prioritized Edge Inclusion (Time: O(E α(N)), Space: O(N))
The optimal solution treats the problem like a connectivity construction task. Use Union-Find (Disjoint Set Union) to track connected components. Edges of type 3 (usable by both Alice and Bob) provide the most value, so process them first and union nodes in both DSU structures simultaneously. Then process type 1 edges for Alice’s DSU and type 2 edges for Bob’s DSU. If a union operation fails because the nodes are already connected, the edge is redundant and can be counted as removable.
The key insight: prioritize shared edges to maximize reuse across both traversals. If you used separate edges first, you might miss opportunities where one edge satisfies both graphs. This greedy ordering guarantees the minimum edges required to keep both graphs connected. The algorithm relies on efficient component merging from graph connectivity theory and the near-constant amortized cost of DSU operations.
After processing all edges, verify that both DSU structures have exactly one connected component. If either graph is disconnected, return -1. Otherwise, the count of redundant edges represents the maximum number of removable edges.
Recommended for interviews: The Union-Find greedy strategy is the expected solution. Interviewers want to see you recognize the similarity to Kruskal-style edge selection and apply prioritized processing of shared edges. Mentioning the brute-force connectivity check shows understanding of the constraints, but implementing the optimized DSU approach demonstrates strong algorithmic design.
Approach 1: Union-Find with Prioritized Edge Inclusion
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to manage the connectivity of nodes. The critical idea is to process edge types in a specific order to ensure that both Alice and Bob can fully traverse the graph while maximizing the number of removable edges:
- Process all type 3 edges first since they can be used by both Alice and Bob, reducing the total number of edges needed to ensure graph connectivity for both.
- Then process type 1 edges for Alice only and type 2 edges for Bob only.
- While processing, count only the edges that result in actual unions, hence contributing to the graph connectivity.
- Ensure after processing, both Alice’s and Bob’s components are fully connected individually.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX, rootY = self.find(x), self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
return False
def is_connected(self):
roots = set(self.find(x) for x in range(len(self.parent)))
return len(roots) == 1
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: list[list[int]]) -> int:
dsu_alice = DSU(n)
dsu_bob = DSU(n)
saved_edges = 0
for t, u, v in edges:
if t == 3:
alice_united = dsu_alice.union(u - 1, v - 1)
bob_united = dsu_bob.union(u - 1, v - 1)
if not alice_united or not bob_united:
saved_edges += 1
for t, u, v in edges:
if t == 1:
if not dsu_alice.union(u - 1, v - 1):
saved_edges += 1
elif t == 2:
if not dsu_bob.union(u - 1, v - 1):
saved_edges += 1
if not dsu_alice.is_connected() or not dsu_bob.is_connected():
return -1
return saved_edgesimport java.util.*;
class DSU {
private int[] parent, rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
public boolean connected() {
Set<Integer> components = new HashSet<>();
for (int i = 0; i < parent.length; i++) {
components.add(find(i));
}
return components.size() == 1;
}
}
public class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
DSU dsuAlice = new DSU(n);
DSU dsuBob = new DSU(n);
int savedEdges = 0;
for (int[] edge : edges) {
if (edge[0] == 3) {
boolean unitedAlice = dsuAlice.union(edge[1] - 1, edge[2] - 1);
boolean unitedBob = dsuBob.union(edge[1] - 1, edge[2] - 1);
if (!unitedAlice || !unitedBob) {
savedEdges++;
}
}
}
DSU dsuCopyAlice = new DSU(n);
DSU dsuCopyBob = new DSU(n);
for (int[] edge : edges) {
if (edge[0] == 1) {
if (!dsuAlice.union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
if (edge[0] == 2) {
if (!dsuBob.union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
}
if (!dsuAlice.connected() || !dsuBob.connected()) {
return -1;
}
return savedEdges;
}
}#include <vector>
#include <numeric>
class DSU {
public:
std::vector<int> parent, rank;
DSU(int n) : parent(n), rank(n, 1) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
};
int maxNumEdgesToRemove(int n, std::vector<std::vector<int>>& edges) {
DSU dsuAlice(n), dsuBob(n);
int savedEdges = 0, types = 0;
for (const auto& edge : edges) {
if (edge[0] == 3) {
bool unitedAlice = dsuAlice.unite(edge[1] - 1, edge[2] - 1);
bool unitedBob = dsuBob.unite(edge[1] - 1, edge[2] - 1);
if (unitedAlice) {
types++;
} else {
savedEdges++;
}
}
}
DSU dsuCopyAlice = dsuAlice, dsuCopyBob = dsuBob;
for (const auto& edge : edges) {
if (edge[0] == 1) {
if (dsuAlice.unite(edge[1] - 1, edge[2] - 1)) {
types++;
} else {
savedEdges++;
}
}
if (edge[0] == 2) {
if (dsuBob.unite(edge[1] - 1, edge[2] - 1)) {
types++;
} else {
savedEdges++;
}
}
}
if (types != (n - 1) * 2) return -1;
return savedEdges;
}class DSU {
constructor(n) {
this.parent = Array.from({ length: n }, (_, index) => index);
this.rank = Array(n).fill(1);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX] += 1;
}
return true;
}
return false;
}
}
var maxNumEdgesToRemove = function(n, edges) {
const dsuAlice = new DSU(n);
const dsuBob = new DSU(n);
let savedEdges = 0;
for (const [type, u, v] of edges) {
if (type === 3) {
const unitedAlice = dsuAlice.union(u - 1, v - 1);
const unitedBob = dsuBob.union(u - 1, v - 1);
if (!unitedAlice && !unitedBob) {
savedEdges++;
}
}
}
for (const [type, u, v] of edges) {
if (type === 1) {
if (!dsuAlice.union(u - 1, v - 1)) {
savedEdges++;
}
} else if (type === 2) {
if (!dsuBob.union(u - 1, v - 1)) {
savedEdges++;
}
}
}
const componentsAlice = new Set(dsuAlice.parent.map(p => dsuAlice.find(p))).size;
const componentsBob = new Set(dsuBob.parent.map(p => dsuBob.find(p))).size;
return (componentsAlice === 1 && componentsBob === 1) ? savedEdges : -1;
};#include <stdio.h>
#include <stdlib.h>
struct DSU {
int *parent, *rank;
int n;
};
// Helper function to initialize the DSU
struct DSU* createDSU(int n) {
struct DSU *dsu = (struct DSU*)malloc(sizeof(struct DSU));
dsu->parent = (int*)malloc(n * sizeof(int));
dsu->rank = (int*)malloc(n * sizeof(int));
dsu->n = n;
for (int i = 0; i < n; ++i) {
dsu->parent[i] = i;
dsu->rank[i] = 1;
}
return dsu;
}
int find(struct DSU *dsu, int x) {
if (dsu->parent[x] != x) {
dsu->parent[x] = find(dsu, dsu->parent[x]);
}
return dsu->parent[x];
}
int unionSet(struct DSU *dsu, int x, int y) {
int rootX = find(dsu, x);
int rootY = find(dsu, y);
if (rootX != rootY) {
if (dsu->rank[rootX] > dsu->rank[rootY]) {
dsu->parent[rootY] = rootX;
} else if (dsu->rank[rootX] < dsu->rank[rootY]) {
dsu->parent[rootX] = rootY;
} else {
dsu->parent[rootY] = rootX;
dsu->rank[rootX] += 1;
}
return 1;
}
return 0;
}
int maxNumEdgesToRemove(int n, int** edges, int edgesSize, int* edgesColSize) {
struct DSU *alice = createDSU(n);
struct DSU *bob = createDSU(n);
int savedEdges = 0;
for (int i = 0; i < edgesSize; ++i) {
if (edges[i][0] == 3) {
if (!unionSet(alice, edges[i][1] - 1, edges[i][2] - 1) || !unionSet(bob, edges[i][1] - 1, edges[i][2] - 1)) {
savedEdges++;
}
}
}
for (int i = 0; i < edgesSize; ++i) {
if (edges[i][0] == 1) {
if (!unionSet(alice, edges[i][1] - 1, edges[i][2] - 1)) {
savedEdges++;
}
}
}
for (int i = 0; i < edgesSize; ++i) {
if (edges[i][0] == 2) {
if (!unionSet(bob, edges[i][1] - 1, edges[i][2] - 1)) {
savedEdges++;
}
}
}
int connectionsA = 0;
int connectionsB = 0;
for (int i = 0; i < n; ++i) {
if (find(alice, i) == i) connectionsA++;
if (find(bob, i) == i) connectionsB++;
}
free(alice->parent);
free(alice->rank);
free(bob->parent);
free(bob->rank);
free(alice);
free(bob);
return (connectionsA > 1 || connectionsB > 1) ? -1 : savedEdges;
}using System;
using System.Collections.Generic;
public class DSU {
private int[] parent, rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int Find(int x) {
if (x != parent[x]) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Union(int x, int y) {
int rootX = Find(x), rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
public class Solution {
public int MaxNumEdgesToRemove(int n, int[][] edges) {
DSU dsuAlice = new DSU(n);
DSU dsuBob = new DSU(n);
int savedEdges = 0;
foreach (var edge in edges) {
if (edge[0] == 3) {
bool unitedAlice = dsuAlice.Union(edge[1] - 1, edge[2] - 1);
bool unitedBob = dsuBob.Union(edge[1] - 1, edge[2] - 1);
if (!unitedAlice || !unitedBob) {
savedEdges++;
}
}
}
foreach (var edge in edges) {
if (edge[0] == 1) {
if (!dsuAlice.Union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
if (edge[0] == 2) {
if (!dsuBob.Union(edge[1] - 1, edge[2] - 1)) {
savedEdges++;
}
}
}
int componentsA = 0, componentsB = 0;
for (int i = 0; i < n; i++) {
if (dsuAlice.Find(i) == i) componentsA++;
if (dsuBob.Find(i) == i) componentsB++;
}
return (componentsA == 1 && componentsB == 1) ? savedEdges : -1;
}
}Using Python, the solution constructs a DSU class for the disjoint set operations. The method maxNumEdgesToRemove loops over the edge list and processes each edge list appropriately using the union-find mechanism, giving priority to edges of type 3.
By calculating which edges are genuinely necessary to maintain full connectivity, it retains a count of saved_edges (i.e., the redundant edges). The final graph configurations for Alice and Bob must show each is completely connected for the operation to succeed (i.e., both DSUs must show only one set when checked).
Time Complexity: O(E * α(n)) due to path-compression and rank technique in Union-Find.
Space Complexity: O(n) attributable to storage of parent and rank structures in DSU instances.
Approach 2: Default Approach
type unionFind struct {
p, size []int
cnt int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size, n}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a-1), uf.find(b-1)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
uf.cnt--
return true
}
func maxNumEdgesToRemove(n int, edges [][]int) (ans int) {
ufa := newUnionFind(n)
ufb := newUnionFind(n)
for _, e := range edges {
t, u, v := e[0], e[1], e[2]
if t == 3 {
if ufa.union(u, v) {
ufb.union(u, v)
} else {
ans++
}
}
}
for _, e := range edges {
t, u, v := e[0], e[1], e[2]
if t == 1 && !ufa.union(u, v) {
ans++
}
if t == 2 && !ufb.union(u, v) {
ans++
}
}
if ufa.cnt == 1 && ufb.cnt == 1 {
return
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find with Prioritized Edge Inclusion | Time Complexity: O(E * α(n)) due to path-compression and rank technique in Union-Find. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Edge Removal + DFS/BFS Connectivity Check | O(E * (V + E)) | O(V) | Conceptual baseline or when demonstrating brute-force reasoning in interviews |
| Union-Find with Prioritized Edge Inclusion | O(E α(N)) | O(N) | Optimal solution for large graphs; standard interview and competitive programming approach |
| Dual DSU with Kruskal-Style Processing | O(E α(N)) | O(N) | Alternative implementation of the same idea emphasizing MST-style edge selection |
Frequently asked questions
Is Remove Max Number of Edges to Keep Graph Fully Traversable easy or hard?
This problem is categorized as Hard because it combines graph connectivity, greedy ordering, and Union-Find implementation. The tricky part is recognizing that shared edges must be processed first to maximize reuse between Alice and Bob's graphs.
Remove Max Number of Edges to Keep Graph Fully Traversable Python/Java solution
Implement two Union-Find structures: one for Alice and one for Bob. Process type 3 edges first and attempt union operations in both DSUs. Then process type 1 edges for Alice and type 2 edges for Bob. If a union fails because nodes are already connected, count that edge as removable.
How to solve Remove Max Number of Edges to Keep Graph Fully Traversable in O(n)?
The problem cannot be solved strictly in O(n) because every edge must be inspected. The closest optimal complexity is O(E α(N)) using Union-Find. Process shared edges first, union components for both Alice and Bob, then handle individual edges while counting redundant ones.
What is the best approach for Remove Max Number of Edges to Keep Graph Fully Traversable?
The best approach uses Union-Find (Disjoint Set Union) with prioritized edge processing. Type 3 edges that both Alice and Bob can use are processed first, then type 1 and type 2 edges for each user separately. This greedy ordering maximizes shared connectivity and identifies redundant edges efficiently. The overall complexity is O(E α(N)) time and O(N) space.
Is Remove Max Number of Edges to Keep Graph Fully Traversable asked at Google/Amazon/Meta?
Graph connectivity and Union-Find problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of disjoint sets, greedy edge selection, and connectivity validation. It is considered a strong signal question for graph fundamentals.
What data structure is used in Remove Max Number of Edges to Keep Graph Fully Traversable?
The core data structure is Union-Find (Disjoint Set Union). It efficiently tracks connected components while edges are added. Path compression and union by rank ensure near-constant time merges and lookups during graph construction.
What is the time complexity of Remove Max Number of Edges to Keep Graph Fully Traversable?
The optimal Union-Find solution runs in O(E α(N)) time, where α(N) is the inverse Ackermann function from path compression and union by rank. This is effectively constant for practical input sizes. Space complexity is O(N) for the disjoint set structures tracking connected components.