Remove Max Number of Edges to Keep Graph Fully Traversable

An undirected graph has n nodes labeled 1 through n. Each entry [type, u, v] in edges describes a road between nodes u and v:

• Type 1 can be used only by Alice.
• Type 2 can be used only by Bob.
• Type 3 can be used by both.

Remove as many edges as possible while keeping every node reachable from every other node for Alice and, separately, for Bob. Return the largest number of edges that can be removed. If either person cannot traverse the entire original graph, return -1.

The same pair of endpoints may have edges of different types. Removing one edge removes only that specific typed edge.

In the diagrams, A marks an Alice-only edge, B a Bob-only edge, and A/B an edge both can use.

Example 1:

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

Output: 3

Explanation: Keep the shared edges 1–2 and 2–3. Both people can traverse all three nodes using these two edges, so remove the other 3. Fewer than two edges cannot connect three nodes.

Example 2:

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

Output: 0

Explanation: Alice needs both type-1 edges, and Bob needs both type-2 edges. There are no shared edges, so every edge is necessary and none can be removed.

Example 3:

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

Output: -1

Explanation: Bob can use only the shared edge 1–2 and cannot reach node 3. Removing edges cannot restore that missing connection, so return -1.

Constraints:

• 1 <= n <= 100000
• 1 <= edges.length <= min(100000, 3 * n * (n - 1) / 2)
• edges[i].length == 3
• 1 <= type <= 3
• 1 <= u < v <= n
• All triples (type, u, v) are distinct.

Topics

Graph Union Find

Company Tags

Please upgrade to NeetCode Pro to view company tags.