Hard
题目描述
Alice 和 Bob 有一个包含 n 个节点的无向图，图中有三种类型的边：
- 类型 1：只能被 Alice 遍历。
- 类型 2：只能被 Bob 遍历。
- 类型 3：Alice 和 Bob 都可以遍历。
给你一个数组 edges，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间有一条类型为 typei 的双向边。请你找到可以删除的最大边数，使得删除这些边之后，图仍然可以被 Alice 和 Bob 完全遍历。如果从任何节点开始，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^5
- 1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2)
- edges[i].length == 3
- 1 <= typei <= 3
- 1 <= ui < vi <= n
- 所有 (typei, ui, vi) 都是不同的。
解题思路
这是一个图论问题，需要使用并查集（Union-Find）数据结构来解决。
核心思想：
- 反向思考：与其考虑删除多少边，不如考虑保留最少多少边能让图连通
- 对于连通图，最少需要 n-1 条边形成生成树
- Alice 和 Bob 各自都需要一个连通图，但可以共享类型 3 的边
算法步骤：
- 优先使用类型 3 的边：因为它们对 Alice 和 Bob 都有用，性价比最高
- 分别为 Alice 和 Bob 建立并查集：
- Alice 可以使用类型 1 和类型 3 的边
- Bob 可以使用类型 2 和类型 3 的边
- 贪心策略：
- 首先处理类型 3 的边，在两个并查集中同时尝试连接
- 然后处理类型 1 和类型 2 的边，分别在对应的并查集中连接
- 统计结果：
- 记录实际使用的边数
- 检查两个图是否都连通（连通分量数是否为 1）
- 返回总边数减去使用的边数
时间复杂度分析：
- 并查集操作近似 O(1)
- 总体时间复杂度为 O(E)，其中 E 是边数
这个算法的关键在于理解类型 3 的边的重要性，以及使用并查集高效地维护连通性。
代码实现
class Solution {
public:
class UnionFind {
public:
vector<int> parent;
int components;
UnionFind(int n) {
parent.resize(n + 1);
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
components = n;
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
parent[px] = py;
components--;
return true;
}
};
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
UnionFind alice(n), bob(n);
int usedEdges = 0;
// First process type 3 edges (can be used by both)
for (auto& edge : edges) {
if (edge[0] == 3) {
bool aliceUsed = alice.unite(edge[1], edge[2]);
bool bobUsed = bob.unite(edge[1], edge[2]);
if (aliceUsed || bobUsed) {
usedEdges++;
}
}
}
// Process type 1 edges (Alice only)
for (auto& edge : edges) {
if (edge[0] == 1 && alice.unite(edge[1], edge[2])) {
usedEdges++;
}
}
// Process type 2 edges (Bob only)
for (auto& edge : edges) {
if (edge[0] == 2 && bob.unite(edge[1], edge[2])) {
usedEdges++;
}
}
// Check if both graphs are fully connected
if (alice.components != 1 || bob.components != 1) {
return -1;
}
return edges.size() - usedEdges;
}
};
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
self.parent[px] = py
self.components -= 1
return True
alice = UnionFind(n)
bob = UnionFind(n)
used_edges = 0
# First process type 3 edges (can be used by both)
for edge_type, u, v in edges:
if edge_type == 3:
alice_used = alice.unite(u, v)
bob_used = bob.unite(u, v)
if alice_used or bob_used:
used_edges += 1
# Process type 1 edges (Alice only)
for edge_type, u, v in edges:
if edge_type == 1 and alice.unite(u, v):
used_edges += 1
# Process type 2 edges (Bob only)
for edge_type, u, v in edges:
if edge_type == 2 and bob.unite(u, v):
used_edges += 1
# Check if both graphs are fully connected
if alice.components != 1 or bob.components != 1:
return -1
return len(edges) - used_edges
public class Solution {
public class UnionFind {
private int[] parent;
public int Components { get; private set; }
public UnionFind(int n) {
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
Components = n;
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Unite(int x, int y) {
int px = Find(x), py = Find(y);
if (px == py) return false;
parent[px] = py;
Components--;
return true;
}
}
public int MaxNumEdgesToRemove(int n, int[][] edges) {
UnionFind alice = new UnionFind(n);
UnionFind bob = new UnionFind(n);
int usedEdges = 0;
// First process type 3 edges (can be used by both)
foreach (var edge in edges) {
if (edge[0] == 3) {
bool aliceUsed = alice.Unite(edge[1], edge[2]);
bool bobUsed = bob.Unite(edge[1], edge[2]);
if (aliceUsed || bobUsed) {
usedEdges++;
}
}
}
// Process type 1 edges (Alice only)
foreach (var edge in edges) {
if (edge[0] == 1 && alice.Unite(edge[1], edge[2])) {
usedEdges++;
}
}
// Process type 2 edges (Bob only)
foreach (var edge in edges) {
if (edge[0] == 2 && bob.Unite(edge[1], edge[2])) {
usedEdges++;
}
}
// Check if both graphs are fully connected
if (alice.Components != 1 || bob.Components != 1) {
return -1;
}
return edges.Length - usedEdges;
}
}
var maxNumEdgesToRemove = function(n, edges) {
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n + 1}, (_, i) => i);
this.components = n;
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const px = this.find(x);
const py = this.find(y);
if (px !== py) {
this.parent[px] = py;
this.components--;
return true;
}
return false;
}
isConnected() {
return this.components === 1;
}
}
const alice = new UnionFind(n);
const bob = new UnionFind(n);
let edgesUsed = 0;
// Sort edges to process type 3 first
edges.sort((a, b) => b[0] - a[0]);
for (const [type, u, v] of edges) {
if (type === 3) {
const aliceUnion = alice.union(u, v);
const bobUnion = bob.union(u, v);
if (aliceUnion || bobUnion) {
edgesUsed++;
}
} else if (type === 1) {
if (alice.union(u, v)) {
edgesUsed++;
}
} else if (type === 2) {
if (bob.union(u, v)) {
edgesUsed++;
}
}
}
if (alice.isConnected() && bob.isConnected()) {
return edges.length - edgesUsed;
}
return -1;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(E × α(N))，其中 E 是边数，N 是节点数，α 是反阿克曼函数，在实际情况下可视为常数 |
| 空间复杂度 | O(N)，用于存储两个并查集的父节点数组 |