在一个神奇的动物牛国度中,生活着许多有趣的动物。Alice 和 Bob 是这个国度中的两位勇士,他们决定一起展开一次探险之旅。他们面前是一个神秘的无向图,图中有 n 个节点和 3 种类型的边: 类型 1:只有 Alice 可以经过的边。 类型 2:只有 Bob 可以经过的边。 类型 3:Alice 和 Bob 都可以经过的边。 他们想要确保无论从哪个节点出发,Alice 和 Bob 都能够遍历到所有其他节点。为了达到这个目标,他们可以删除一些边。删除边后,他们希望仍然能够完成完全的探险之旅。 请你编写一个函数 int maxRemovableEdges(int n, vector& edges),来帮助 Alice 和 Bob 计算可以删除的最大边数。如果无论如何删除边,Alice 和 Bob 仍然无法完全遍历图,则返回 -1。 函数输入参数: n:一个整数,表示节点的个数。 edges:一个二维整数数组,表示边的信息。每个元素 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。边的类型 typei 可以是 1、2 或 3,正好对应上述三种情况。 函数输出: 返回一个整数,表示可以删除的最大边数。如果无论如何删除边,Alice 和 Bob 仍然无法完全遍历图,则返回 -1。
示例1
输入
4,[[3, 1, 2],[3, 2, 3],[1, 1, 3],[1, 2, 4],[1, 1, 2],[2, 3, 4]]
示例2
输入
5,[[3, 1, 2],[3, 2, 3],[3, 3, 4],[3, 4, 5],[1, 1, 3],[1, 2, 4],[1, 3, 5]]
备注:
1 1 edges[i].length == 31 1 所有元组 (typei, ui, vi) 互不相同
加载中...