 All Problems
Remove Max Number of Edges to Keep Graph Fully Traversable
hard
union-find
graph
google
amazon

Alice and Bob have an undirected graph with n nodes and three types of edges:

  • Type 1: traversable by Alice only
  • Type 2: traversable by Bob only
  • Type 3: traversable by both

Return the maximum number of edges you can remove so that the graph is still fully traversable by both Alice and Bob. Return -1 if it's 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

Constraints:

  • 1 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, 3*n*(n-1)/2)
Run to check your code against the sample cases, or submit to run every case