#1579
Remove Max Number of Edges to Keep Graph Fully Traversable
specialist · 990 · lc hard +32 · verified · 70.2% accepted · 2,681 likes · top 79%
Description
You have an undirected graph of n nodes and edges of three types:
- Type 1: traversable by Alice only.
- Type 2: traversable by Bob only.
- Type 3: traversable by both Alice and Bob.
Given an array edges where edges[i] = [typei, ui, vi], remove as many edges as possible while preserving each player's ability to reach all nodes. Return the maximum number of removable edges, or -1 if full traversal for both is impossible.
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.
Code
1
2
3