1579. Remove Max Number of Edges to Keep Graph Fully Traversable

题目信息

题号:

1579

难度:

Hard

主题:

图、并查集、最小生成结构

原题:

LeetCode 1579

重点:

类型一仅 Alice 可用,类型二仅 Bob 可用,类型三两人都可用;删除最多边后两人的图都必须连通

题目重述

有 n 个节点和三类无向边:类型 1 只能由 Alice 使用,类型 2 只能由 Bob 使用,类型 3 两人都可使用。

请删除尽可能多的边,同时保证 Alice 和 Bob 各自仍能从任意节点到达其他所有节点。返回最多可删除边数;若无法同时保证两人完全可遍历,返回 -1。

1 <= n <= 10^5,1 <= edges.length <= min(10^5,3*n*(n-1)/2)。

自建示例

共享边已经连通全图时专属边可以删除:

输入:n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[2,2,4],[3,1,4]]
输出:2
解释:三条类型三边已连接全部节点,类型一和类型二边都可删除。

两人的可用边分别缺少连通路径时无解:

输入:n = 3, edges = [[1,1,2],[2,2,3]]
输出:-1
解释:Alice 无法到达节点 3,Bob 无法到达节点 1。