问题描述
给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。
请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。
请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。
示例 1：
输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。
注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
示例 2 ：
输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。
提示：
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= fromi < toi < n1 <= weighti <= 1000- 所有
(fromi, toi) 数对都是互不相同的。
解题思路
若某条边是关键边，则删去该条边后，剩下的边不能使所有顶点连通，或者形成的最小生成树的代价比最小代价大。
若某条边是伪关键边，首先它不是关键边，然后包含这条边的最小生成树的代价与最小代价相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 | class UnionFind:
def __init__(self):
self.fa = None
self.size = None
def init_set(self, n: int) -> None:
self.fa = list(range(n))
self.size = [1] * n
def find_set(self, x: int) -> int:
if x != self.fa[x]:
self.fa[x] = self.find_set(self.fa[x])
return self.fa[x]
def union_set(self, x: int, y: int) -> bool:
x, y = self.find_set(x), self.find_set(y)
if x == y: return False
if self.size[x] < self.size[y]: x, y = y, x
self.fa[y] = x
self.size[x] += self.size[y]
return True
def is_connected(self, x: int, y: int) -> bool:
return self.find_set(x) == self.find_set(y)
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, e: List[List[int]]) -> List[List[int]]:
m = len(e)
index = list(range(m))
index.sort(key=lambda i: e[i][2])
min_cost = 0
uf = UnionFind()
uf.init_set(n)
for i in index:
if uf.union_set(e[i][0], e[i][1]):
min_cost += e[i][2]
ans = [[], []]
for i in index:
uf.init_set(n)
cost = cnt = 0
for j in index:
if j != i and uf.union_set(e[j][0], e[j][1]):
cost += e[j][2]
cnt += 1
if cnt != n - 1 or cost > min_cost:
ans[0].append(i)
continue
uf.init_set(n)
uf.union_set(e[i][0], e[i][1])
cost = e[i][2]
for j in index:
if j != i and uf.union_set(e[j][0], e[j][1]):
cost += e[j][2]
if cost == min_cost:
ans[1].append(i)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 | class UnionFind {
public:
vector<int> fa, size;
void init_set(int n) {
fa.resize(n), size.resize(n);
for (int i = 0; i < n; ++i) { fa[i] = i, size[i] = 1; }
}
int find_set(int x) { return x == fa[x] ? x : (fa[x] = find_set(fa[x])); }
bool union_set(int x, int y) {
x = find_set(x), y = find_set(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
fa[y] = x, size[x] += size[y];
return true;
}
bool is_connected(int x, int y) { return find_set(x) == find_set(y); }
};
class Solution {
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& e) {
int m = e.size();
int min_cost = 0, cost, cnt;
auto uf = UnionFind(); uf.init_set(n);
vector<int> index(m);
iota(index.begin(), index.end(), 0);
sort(index.begin(), index.end(), [&] (const auto &i, const auto &j) { return e[i][2] < e[j][2]; });
for (auto i : index) {
if (uf.union_set(e[i][0], e[i][1])) min_cost += e[i][2];
}
vector<vector<int>> ans(2);
for (auto i : index) {
uf.init_set(n), cost = 0, cnt = 0;
for (auto j : index) {
if (j != i && uf.union_set(e[j][0], e[j][1])) cost += e[j][2], ++cnt;
}
if (cnt != n - 1 || cost > min_cost) {
ans[0].emplace_back(i);
continue;
}
uf.init_set(n), uf.union_set(e[i][0], e[i][1]), cost = e[i][2];
for (auto j : index) {
if (j != i && uf.union_set(e[j][0], e[j][1])) cost += e[j][2];
}
if (cost == min_cost) ans[1].emplace_back(i);
}
return ans;
}
};
|