Remove Max Number of Edges to Keep Graph Fully Traversable

Remove Max Number of Edges to Keep Graph Fully Traversable - 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] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i between nodes u_i and v_i, 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.

Input & Output

Example 1 — Basic Graph

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

› Output: 2

💡 Note: Alice needs edges connecting all nodes using type 1 and 3. Bob needs edges using type 2 and 3. The minimum spanning trees need 4 edges total (3 for connectivity + 1 extra for different requirements), so we can remove 6 - 4 = 2 edges.

Example 2 — Impossible Case

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

› Output: -1

💡 Note: Alice cannot reach node 4 from nodes 1,2,3 using type 1 and 3 edges. Bob cannot reach node 1 from other nodes using type 2 and 3 edges. Full traversal is impossible.

Example 3 — All Shared Edges

$ Input: n = 3, edges = [[3,1,2],[3,2,3],[3,1,3]]

› Output: 1

💡 Note: All edges are type 3 (shared). We need only 2 edges to connect 3 nodes (minimum spanning tree), so we can remove 3 - 2 = 1 edge.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ edges.length ≤ min(10⁵, 3 * n * (n - 1) / 2)
edges[i].length == 3
1 ≤ type_i ≤ 3
1 ≤ u_i < v_i ≤ n
All tuples (type_i, u_i, v_i) are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with 3 types of edges: Alice-only, Bob-only, and shared

Find Minimum

Use Union-Find to determine minimum edges needed for connectivity

Calculate Result

Maximum removable = Total edges - Minimum required

Key Takeaway

🎯 Key Insight: Prioritize shared edges first since they help both Alice and Bob simultaneously, then use Union-Find to track minimum spanning trees

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use Union-Find with greedy edge selection. Process type 3 (shared) edges first since they help both Alice and Bob simultaneously. Then add type 1 and type 2 edges only when needed to maintain connectivity. Best approach uses Union-Find: Time O(m×α(n)), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^m × (m + n))	O(n + m)	Try every possible subset of edges to find maximum removable
Union-Find with Greedy Edge Selection	O(m × α(n))	O(n)	Use Union-Find to greedily build minimum spanning forest, prioritizing shared edges

Brute Force - Try All Combinations — Algorithm Steps

Generate all 2^m possible edge subsets
For each subset, check if Alice can traverse all nodes
Check if Bob can traverse all nodes
Track minimum edges needed for valid traversal

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^m possible combinations of edges

Check Connectivity

For each subset, verify Alice and Bob can traverse all nodes

Find Minimum

Track smallest valid edge set, return total - minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

typedef struct {
    int* data;
    int size;
    int capacity;
} Stack;

Stack* createStack() {
    Stack* stack = malloc(sizeof(Stack));
    stack->capacity = 1000;
    stack->data = malloc(stack->capacity * sizeof(int));
    stack->size = 0;
    return stack;
}

void push(Stack* stack, int val) {
    stack->data[stack->size++] = val;
}

int pop(Stack* stack) {
    return stack->data[--stack->size];
}

bool isEmpty(Stack* stack) {
    return stack->size == 0;
}

bool canTraverse(int edges[][3], int edgeCount, int n, int type1, int type2) {
    if (edgeCount == 0) return n <= 1;
    
    // Build adjacency list
    int** graph = malloc((n + 1) * sizeof(int*));
    int* graphSize = calloc(n + 1, sizeof(int));
    for (int i = 0; i <= n; i++) {
        graph[i] = malloc(1000 * sizeof(int));
    }
    
    for (int i = 0; i < edgeCount; i++) {
        if (edges[i][0] == type1 || edges[i][0] == type2) {
            int u = edges[i][1], v = edges[i][2];
            graph[u][graphSize[u]++] = v;
            graph[v][graphSize[v]++] = u;
        }
    }
    
    // DFS from node 1
    bool* visited = calloc(n + 1, sizeof(bool));
    Stack* stack = createStack();
    push(stack, 1);
    visited[1] = true;
    int count = 1;
    
    while (!isEmpty(stack)) {
        int node = pop(stack);
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                push(stack, neighbor);
                count++;
            }
        }
    }
    
    // Cleanup
    for (int i = 0; i <= n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    free(visited);
    free(stack->data);
    free(stack);
    
    return count == n;
}

int solution(int n, int edges[][3], int m) {
    int minEdges = INT_MAX;
    
    // Try all possible subsets (limited for practicality)
    for (int mask = 0; mask < (1 << (m < 20 ? m : 20)); mask++) {
        int selectedEdges[1000][3];
        int selectedCount = 0;
        
        for (int i = 0; i < (m < 20 ? m : 20); i++) {
            if (mask & (1 << i)) {
                selectedEdges[selectedCount][0] = edges[i][0];
                selectedEdges[selectedCount][1] = edges[i][1];
                selectedEdges[selectedCount][2] = edges[i][2];
                selectedCount++;
            }
        }
        
        // Check Alice (type 1 and 3)
        if (!canTraverse(selectedEdges, selectedCount, n, 1, 3)) continue;
        
        // Check Bob (type 2 and 3)
        if (!canTraverse(selectedEdges, selectedCount, n, 2, 3)) continue;
        
        if (selectedCount < minEdges) {
            minEdges = selectedCount;
        }
    }
    
    return minEdges == INT_MAX ? -1 : m - minEdges;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for small test cases
    int edges[1000][3];
    int m = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    // Basic parsing - extract numbers
    char* ptr = line;
    while (*ptr && m < 1000) {
        if (*ptr == '[') {
            ptr++;
            edges[m][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            edges[m][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            edges[m][2] = atoi(ptr);
            m++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, edges, m);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m × (m + n))

2^m subsets, each requiring O(m+n) time for connectivity check using DFS

✓ Linear Growth

Space Complexity

O(n + m)

Space for recursion stack in DFS and temporary edge storage

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler