【刷穿 LeetCode】1579. 保证图可完全遍历（困难）
【刷穿 LeetCode】1579. 保证图可完全遍历（困难）
题目描述
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：
- 类型 1：只能由 Alice 遍历。
- 类型 2：只能由 Bob 遍历。
- 类型 3：Alice 和 Bob 都可以遍历。
给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
示例 1：
输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。
示例 2：
输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。
示例 3：
输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。
提示：
1 <= n <= 10^51 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)edges[i].length == 31 <= edges[i][0] <= 31 <= edges[i][1] < edges[i][2] <= n- 所有元组
(typei, ui, vi)互不相同
贪心 + 并查集解法
首先使用 p1 和 p2 来分别表示 Alice 和 Bob 的并查集。
对 edges 数组进行排序，将共同的边放到前面，优先处理。
使用集合 s1 和 s2 存储对于 Alice 和 Bob 而言多余的边。
遍历 edges 进行分情况讨论：
type = 3的公共边：根据对应的「并查集」连通性来判断是否为多余边，若是多余边则加入对应的集合内type = 2或type = 1独有边：根据对应的「并查集」连通性来判断是否为多余边，若是多余边则直接计数（直接删除）
遍历完后，检查两个「并查集」的整体连通性，若是不连通，则返回 -1；若联通则对 s1 和 s2 取交集大小加入计数，返回答案：
class Solution {
int[] p1 = new int[100009];
int[] p2 = new int[100009];
void union(int[] p, int a, int b) {
p[find(p, a)] = p[find(p, b)];
}
int find(int[] p, int x) {
if (p[x] != x) p[x] = find(p, p[x]);
return p[x];
}
boolean query(int[] p, int a, int b) {
return find(p, a) == find(p, b);
}
public int maxNumEdgesToRemove(int n, int[][] edges) {
for (int i = 1; i <= n; i++) {
p1[i] = i;
p2[i] = i;
}
Arrays.sort(edges, (a,b)->b[0]-a[0]);
int ans = 0;
Set<int[]> s1 = new HashSet<>(), s2 = new HashSet<>();
for (int[] edge : edges) {
int type = edge[0], a = edge[1], b = edge[2];
if (type == 1) {
if (!query(p1, a, b)) {
union(p1, a, b);
} else {
ans++;
}
} else if (type == 2) {
if (!query(p2, a, b)) {
union(p2, a, b);
} else {
ans++;
}
} else {
if (!query(p1, a, b)) {
union(p1, a, b);
} else {
s1.add(edge);
}
if (!query(p2, a, b)) {
union(p2, a, b);
} else {
s2.add(edge);
}
}
}
for (int i = 1; i <= n; i++) {
if (!query(p1, 1, i)) return -1;
if (!query(p2, 1, i)) return -1;
}
Set<int[]> set = new HashSet<>();
set.addAll(s1);
set.retainAll(s2);
ans += set.size();
return ans;
}
}
- 时间复杂度：节点的数量为
n，边的数量为m。排序的复杂度为
；使用并查集处理边的复杂度为
；初始化并查集，检查连通性复杂度为
。整体复杂度为
O(m\log{m})
O(n)
- 空间复杂度：
注意：Java 的 Arrays.sort() 并不只有双轴快排一种实现。这里假定了 Arrays.sort() 使用的是双轴快排。
证明
我们来证明一下，为什么「优先保留公共边」这样的做法是对的。
由于求的是「删除边的最大数量」，假设这样的思路做法得到的答案是 ans，而真实的最优解是 max。
首先要明确，我们的做法是：如果一条边能够使得未联通的节点联通，那么我们就保留并使用这条边。
这样的做法肯定是能够得到合法值的。
换句话说，如果给定边能实现两个并查集联通的话，最终我们必定能够使两个并查集联通。
因此 ans 必然是一个合法值，由于最优解是最大值 max ，所以我们天然有 ans<=max。
只要我们再证明 ans>=max 成立，即可证明 ans=max，我们的做法能得到最优解。
接下来，使用反证法来证明 ans>=max 成立：
假设 ans>=max 不成立，则有 ans<max ，也就是我们比最优解少删除了一些边。
假设我们的删除方案如下，不同形状代表不同类型的边，黑色代表在方案 ans 中被删除的边。
由于我们的删除逻辑是只有没贡献的边才会被删除，所以当前保留的边，对于这个遍历顺序而言，都是必须的。
我们分情况来讨论:
单纯的少删除了某些边：也就是某些边应该要删除才对（例如上图的某些蓝点应该为黑色）： 但这显然是和我们的逻辑是冲突的。因为我们在对某条边进行删除操作之前，先确认了该边的点已经是联通状态，该边的保留不会对连通性产生贡献。因此单纯的少删除了某些边这种可能性显然不可能发生，所有的蓝点都应该是保留才对。有更好替代方案：意思是可能会存在删除更多的边能达到同样的连通性效果（不失一般性的，假如我们删除#的两条边，保留任意一个黑点的边，仍然能够实现联通效果）： 这也是和我们的逻辑是冲突的，假如额外删除了#的边，由于一条能够联通 2 个节点，而逻辑保证了所有的蓝点不可能是重边，所以额外删除两条边，至少会导致 3 个点由联通变为不联通。而新保留的黑点的边，最多能够连接 2 个节点。因此至少会导致一个节点从联通变为不连通。因此有更好替代方案这种情况也不可能。 同时因为这一推论与#和 黑点的相对位置无关，因此能推广到任意的类型的边。
总结
这是我用到「数组实现并查集」的模板代码。
使用数组实现并查集相比于类模板，代码更少，更好拓展，也能减少对象创建的额外消耗：
class Solution {
// 数组长度视数据范围而定
int[] p = new int[1010];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
p[find(a)] = find(b);
}
boolean query(int a, int b) {
return find(a) == find(b);
}
public void main(int[] n) {
// 别忘了先初始化，再使用
for (int i = 1; i <= n; i++) p[i] = i;
...
}
}
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
腾讯云开发者
