Skip to content
RED SAGSkills
hard60 ptsunion-findgraphgreedy

Prune Links Two Teams Share

A data centre has n servers numbered 1 to n. Each entry [type, a, b] of links is a two-way link between servers a and b:

- type 1: only the Blue team can use it, - type 2: only the Green team can use it, - type 3: both teams can use it.

To cut costs, links will be removed, but afterwards each team must still be able to reach every server from every other server using the links it may use. Return the maximum number of links that can be removed, or -1 if even with all links one of the teams cannot reach every server.

Example 1

Input: n = 3, links = [[3,1,2],[1,2,3],[2,2,3],[1,1,3]]
Output: 1
Explanation: Keep the shared 1-2, Blue 2-3 and Green 2-3; Blue 1-3 is redundant.

Example 2

Input: n = 3, links = [[1,1,2],[1,2,3],[2,1,2]]
Output: -1
Explanation: Green has no way to reach server 3.

Constraints

  • 1 <= n <= 5000
  • 0 <= links.length <= 2.5 * 10^4
  • 1 <= type <= 3
  • 1 <= a, b <= n, a != b
Hint 1

Shared links are the most valuable: add every useful type-3 link to both teams first.

Hint 2

Then add type-1 links to Blue only and type-2 links to Green only, using union-find to skip any link that joins already connected servers.

Discussion 0

Join free to post in the discussion.

Good practice for: DevOps Engineer, Cloud Engineer, Site Reliability Engineer, Backend Developer, Blockchain Developer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.