Remove Max Number of Edges to Keep Graph Fully Traversable

Problem Statement

Alice and Bob share an undirected graph which contains a mix of edges categorized into three types based on their traversal permissions:

• Type 1 edges can only be traversed by Alice.
• Type 2 edges are accessible only to Bob.
• Type 3 edges can be utilized by both Alice and Bob.

This graph is defined using an array called edges, where each element, represented as [typei, ui, vi], denotes an edge of type typei that connects nodes ui and vi. The goal is to find the maximum number of edges that can be removed from this graph while ensuring that the graph still remains traversable by both Alice and Bob, from any node to any other node. If it's impossible for both Alice and Bob to traverse the entire graph, even without removing any edges, the result should be -1.

Examples

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 <= 105
• 1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
• edges[i].length == 3
• 1 <= typei <= 3
• 1 <= ui < vi <= n
• All tuples (typei, ui, vi) are distinct.

Approach and Intuition

To solve this problem, we need an understanding of graph theory, particularly concepts of connectivity and spanning trees. Here’s a step-by-step breakdown of the approach:

1. Initial Validation: Check if the graph can be fully traversed by Alice and Bob without any removals. If not, return -1.

2. Edge Priority: Prioritize the use of type 3 edges (usable by both) to maximize the common paths they share in the graph, as this will allow more flexibility in removing type 1 and type 2 edges later on.

3. Utilizing Union-Find or DFS: A union-find data structure or depth-first search (DFS) can be employed to determine the connected components in the graph:

   • For Alice-only and Bob-only graphs constructed using type 1 and type 2 edges respectively, ensure each is initially a spanning tree, i.e., a minimum structure where all nodes are connected without cycles.
   • For the mixed graph using type 3 edges, again ensure it forms a minimum spanning tree.

4. Edge Reduction: After the minimum spanning structure is maintained, further edges (especially those of type 1 and type 2) that do not contribute to connectivity can be removed.

5. Counting and Comparison: Throughout these operations, keep a count of removable edges. After achieving the spanning structures while integrating as many type 3 edges as possible, compare the reduction count to the maximum number possible while maintaining full traversal capabilities.

The union-find approach is particularly efficient here because it allows for quick union and find operations that help in seamlessly determining and merging connected components, essential for analyzing and adjusting the graph's connectivity dynamically as edges are considered for removal.

Given these matrices, we iteratively adjust the graph, ensuring after each removal step, both Alice and Bob can still traverse the entire graph. If at any step removing more edges violates this requirement, we halt and take the current count as the maximum number of removable edges without breaking traversability.

Solutions

class DisjointSet {
    vector<int> parent;
    vector<int> rank;
    int count;
    
public:
    DisjointSet(int size) {
        count = size;
        for (int i = 0; i <= size; i++) {
            parent.push_back(i);
            rank.push_back(1);
        }
    }
        
    int find(int node) {
        if (parent[node] == node) {
            return node;
        }
            
        return parent[node] = find(parent[node]);
    }
        
    int unionSets(int node1, int node2) {       
        int root1 = find(node1);
        int root2 = find(node2);
            
        if (root1 == root2) {
            return 0;
        }
            
        if (rank[root1] > rank[root2]) {
            rank[root1] += rank[root2];
            parent[root2] = root1;
        } else {
            rank[root2] += rank[root1];
            parent[root1] = root2;
        }
            
        count--;
        return 1;
    }
        
    bool allConnected() {
        return count == 1;
    }
};
    
class Solution {
public:
    int maximumEdgesToRemove(int n, vector<vector<int>>& edges) {
        DisjointSet Alice(n), Bob(n);
    
        int includedEdges = 0;
    
        for (vector<int>& edge : edges) {
            if (edge[0] == 3) {
                includedEdges += (Alice.unionSets(edge[1], edge[2]) | Bob.unionSets(edge[1], edge[2]));
            }
        }
    
        for (vector<int>& edge : edges) {
            if (edge[0] == 1) {
                includedEdges += Alice.unionSets(edge[1], edge[2]);
            }
            else if (edge[0] == 2) {
                includedEdges += Bob.unionSets(edge[1], edge[2]);
            }
        }
    
        if (Alice.allConnected() && Bob.allConnected()) {
            return edges.size() - includedEdges;
        }
            
        return -1;
    }
};