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)``。 自建示例 -------- 共享边已经连通全图时专属边可以删除: .. code-block:: text 输入:n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[2,2,4],[3,1,4]] 输出:2 解释:三条类型三边已连接全部节点,类型一和类型二边都可删除。 两人的可用边分别缺少连通路径时无解: .. code-block:: text 输入:n = 3, edges = [[1,1,2],[2,2,3]] 输出:-1 解释:Alice 无法到达节点 3,Bob 无法到达节点 1。