/**
* @param {number} n
* @param {number[][]} edges
* @return {number[][]}
*/
var findCriticalAndPseudoCriticalEdges = function(n, edges) {
const m = edges.length;
for (const [i, edge] of edges.entries()) {
edge.push(i);
}
edges.sort((a, b) => a[2] - b[2]);
// 计算 value
const uf_std = new UnionFind(n);
let value = 0;
for (let i = 0; i < m; i++) {
if (uf_std.unite(edges[i][0], edges[i][1])) {
value += edges[i][2];
}
}
const ans = [[], []];
for (let i = 0; i < m; i++) {
// 判断是否是关键边
let uf = new UnionFind(n);
let v = 0;
for (let j = 0; j < m; j++) {
if (i !== j && uf.unite(edges[j][0], edges[j][1])) {
v += edges[j][2];
}
}
if (uf.setCount !== 1 || (uf.setCount === 1 && v > value)) {
ans[0].push(edges[i][3]);
continue;
}
// 判断是否是伪关键边
uf = new UnionFind(n);
uf.unite(edges[i][0], edges[i][1]);
v = edges[i][2];
for (let j = 0; j < m; j++) {
if (i !== j && uf.unite(edges[j][0], edges[j][1])) {
v += edges[j][2];
}
}
if (v === value) {
ans[1].push(edges[i][3]);
}
}
return ans;
};
// 并查集模板
class UnionFind {
constructor (n) {
this.parent = new Array(n).fill(0).map((element, index) => index);
this.size = new Array(n).fill(1);
// 当前连通分量数目
this.setCount = n;
}
findset (x) {
if (this.parent[x] === x) {
return x;
}
this.parent[x] = this.findset(this.parent[x]);
return this.parent[x];
}
unite (a, b) {
let x = this.findset(a), y = this.findset(b);
if (x === y) {
return false;
}
if (this.size[x] < this.size[y]) {
[x, y] = [y, x];
}
this.parent[y] = x;
this.size[x] += this.size[y];
this.setCount -= 1;
return true;
}
connected (a, b) {
const x = this.findset(a), y = this.findset(b);
return x === y;
}
}
# 并查集模板
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
self.n = n
# 当前连通分量数目
self.setCount = n
def findset(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.findset(self.parent[x])
return self.parent[x]
def unite(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
def connected(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
return x == y
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
m = len(edges)
for i, edge in enumerate(edges):
edge.append(i)
edges.sort(key=lambda x: x[2])
# 计算 value
uf_std = UnionFind(n)
value = 0
for i in range(m):
if uf_std.unite(edges[i][0], edges[i][1]):
value += edges[i][2]
ans = [list(), list()]
for i in range(m):
# 判断是否是关键边
uf = UnionFind(n)
v = 0
for j in range(m):
if i != j and uf.unite(edges[j][0], edges[j][1]):
v += edges[j][2]
if uf.setCount != 1 or (uf.setCount == 1 and v > value):
ans[0].append(edges[i][3])
continue
# 判断是否是伪关键边
uf = UnionFind(n)
uf.unite(edges[i][0], edges[i][1])
v = edges[i][2]
for j in range(m):
if i != j and uf.unite(edges[j][0], edges[j][1]):
v += edges[j][2]
if v == value:
ans[1].append(edges[i][3])
return ans
class Solution {
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int m = edges.length;
int[][] newEdges = new int[m][4];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
newEdges[i][j] = edges[i][j];
}
newEdges[i][3] = i;
}
Arrays.sort(newEdges, new Comparator<int[]>() {
public int compare(int[] u, int[] v) {
return u[2] - v[2];
}
});
// 计算 value
UnionFind ufStd = new UnionFind(n);
int value = 0;
for (int i = 0; i < m; ++i) {
if (ufStd.unite(newEdges[i][0], newEdges[i][1])) {
value += newEdges[i][2];
}
}
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (int i = 0; i < 2; ++i) {
ans.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; ++i) {
// 判断是否是关键边
UnionFind uf = new UnionFind(n);
int v = 0;
for (int j = 0; j < m; ++j) {
if (i != j && uf.unite(newEdges[j][0], newEdges[j][1])) {
v += newEdges[j][2];
}
}
if (uf.setCount != 1 || (uf.setCount == 1 && v > value)) {
ans.get(0).add(newEdges[i][3]);
continue;
}
// 判断是否是伪关键边
uf = new UnionFind(n);
uf.unite(newEdges[i][0], newEdges[i][1]);
v = newEdges[i][2];
for (int j = 0; j < m; ++j) {
if (i != j && uf.unite(newEdges[j][0], newEdges[j][1])) {
v += newEdges[j][2];
}
}
if (v == value) {
ans.get(1).add(newEdges[i][3]);
}
}
return ans;
}
}
// 并查集模板
class UnionFind {
int[] parent;
int[] size;
int n;
// 当前连通分量数目
int setCount;
public UnionFind(int n) {
this.n = n;
this.setCount = n;
this.parent = new int[n];
this.size = new int[n];
Arrays.fill(size, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
public int findset(int x) {
return parent[x] == x ? x : (parent[x] = findset(parent[x]));
}
public boolean unite(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
int temp = x;
x = y;
y = temp;
}
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
public boolean connected(int x, int y) {
x = findset(x);
y = findset(y);
return x == y;
}
}
# 并查集模板
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
self.n = n
# 当前连通分量数目
self.setCount = n
def findset(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.findset(self.parent[x])
return self.parent[x]
def unite(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
def connected(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
return x == y
# Tarjan 算法求桥边模版
class TarjanSCC:
def __init__(self, n: int, edges: List[List[int]], edgesId: List[List[int]]):
self.n = n
self.edges = edges
self.edgesId = edgesId
self.low = [-1] * n
self.dfn = [-1] * n
self.ans = list()
self.ts = -1
def getCuttingEdge(self) -> List[int]:
for i in range(self.n):
if self.dfn[i] == -1:
self.pGetCuttingEdge(i, -1)
return self.ans
def pGetCuttingEdge(self, u: int, parentEdgeId: int):
self.ts += 1
self.low[u] = self.dfn[u] = self.ts
for v, iden in zip(self.edges[u], self.edgesId[u]):
if self.dfn[v] == -1:
self.pGetCuttingEdge(v, iden)
self.low[u] = min(self.low[u], self.low[v])
if self.low[v] > self.dfn[u]:
self.ans.append(iden)
elif iden != parentEdgeId:
self.low[u] = min(self.low[u], self.dfn[v])
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
m = len(edges)
for i, edge in enumerate(edges):
edge.append(i)
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans0 = list()
label = [0] * m
i = 0
while i < m:
# 找出所有权值为 w 的边，下标范围为 [i, j)
w = edges[i][2]
j = i
while j < m and edges[j][2] == edges[i][2]:
j += 1
# 存储每个连通分量在图 G 中的编号
compToId = dict()
# 图 G 的节点数
gn = 0
for k in range(i, j):
x = uf.findset(edges[k][0])
y = uf.findset(edges[k][1])
if x != y:
if x not in compToId:
compToId[x] = gn
gn += 1
if y not in compToId:
compToId[y] = gn
gn += 1
else:
# 将自环边标记为 -1
label[edges[k][3]] = -1
# 图 G 的边
gm = collections.defaultdict(list)
gmid = collections.defaultdict(list)
for k in range(i, j):
x = uf.findset(edges[k][0])
y = uf.findset(edges[k][1])
if x != y:
idx, idy = compToId[x], compToId[y]
gm[idx].append(idy)
gmid[idx].append(edges[k][3])
gm[idy].append(idx)
gmid[idy].append(edges[k][3])
bridges = TarjanSCC(gn, gm, gmid).getCuttingEdge()
# 将桥边（关键边）标记为 1
ans0.extend(bridges)
for iden in bridges:
label[iden] = 1
for k in range(i, j):
uf.unite(edges[k][0], edges[k][1])
i = j
# 未标记的边即为非桥边（伪关键边）
ans1 = [i for i in range(m) if label[i] == 0]
return [ans0, ans1]
class Solution {
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int m = edges.length;
int[][] newEdges = new int[m][4];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
newEdges[i][j] = edges[i][j];
}
newEdges[i][3] = i;
}
Arrays.sort(newEdges, new Comparator<int[]>() {
public int compare(int[] u, int[] v) {
return u[2] - v[2];
}
});
UnionFind uf = new UnionFind(n);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (int i = 0; i < 2; ++i) {
ans.add(new ArrayList<Integer>());
}
int[] label = new int[m];
for (int i = 0; i < m;) {
// 找出所有权值为 w 的边，下标范围为 [i, j)
int w = newEdges[i][2];
int j = i;
while (j < m && newEdges[j][2] == newEdges[i][2]) {
++j;
}
// 存储每个连通分量在图 G 中的编号
Map<Integer, Integer> compToId = new HashMap<Integer, Integer>();
// 图 G 的节点数
int gn = 0;
for (int k = i; k < j; ++k) {
int x = uf.findset(newEdges[k][0]);
int y = uf.findset(newEdges[k][1]);
if (x != y) {
if (!compToId.containsKey(x)) {
compToId.put(x, gn++);
}
if (!compToId.containsKey(y)) {
compToId.put(y, gn++);
}
} else {
// 将自环边标记为 -1
label[newEdges[k][3]] = -1;
}
}
// 图 G 的边
List<Integer>[] gm = new List[gn];
List<Integer>[] gmid = new List[gn];
for (int k = 0; k < gn; ++k) {
gm[k] = new ArrayList<Integer>();
gmid[k] = new ArrayList<Integer>();
}
for (int k = i; k < j; ++k) {
int x = uf.findset(newEdges[k][0]);
int y = uf.findset(newEdges[k][1]);
if (x != y) {
int idx = compToId.get(x), idy = compToId.get(y);
gm[idx].add(idy);
gmid[idx].add(newEdges[k][3]);
gm[idy].add(idx);
gmid[idy].add(newEdges[k][3]);
}
}
List<Integer> bridges = new TarjanSCC(gn, gm, gmid).getCuttingEdge();
// 将桥边（关键边）标记为 1
for (int id : bridges) {
ans.get(0).add(id);
label[id] = 1;
}
for (int k = i; k < j; ++k) {
uf.unite(newEdges[k][0], newEdges[k][1]);
}
i = j;
}
// 未标记的边即为非桥边（伪关键边）
for (int i = 0; i < m; ++i) {
if (label[i] == 0) {
ans.get(1).add(i);
}
}
return ans;
}
}
// 并查集模板
class UnionFind {
int[] parent;
int[] size;
int n;
// 当前连通分量数目
int setCount;
public UnionFind(int n) {
this.n = n;
this.setCount = n;
this.parent = new int[n];
this.size = new int[n];
Arrays.fill(size, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
public int findset(int x) {
return parent[x] == x ? x : (parent[x] = findset(parent[x]));
}
public boolean unite(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
int temp = x;
x = y;
y = temp;
}
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
public boolean connected(int x, int y) {
x = findset(x);
y = findset(y);
return x == y;
}
}
class TarjanSCC {
List<Integer>[] edges;
List<Integer>[] edgesId;
int[] low;
int[] dfn;
List<Integer> ans;
int n;
int ts;
public TarjanSCC(int n, List<Integer>[] edges, List<Integer>[] edgesId) {
this.edges = edges;
this.edgesId = edgesId;
this.low = new int[n];
Arrays.fill(low, -1);
this.dfn = new int[n];
Arrays.fill(dfn, -1);
this.n = n;
this.ts = -1;
this.ans = new ArrayList<Integer>();
}
public List<Integer> getCuttingEdge() {
for (int i = 0; i < n; ++i) {
if (dfn[i] == -1) {
getCuttingEdge(i, -1);
}
}
return ans;
}
private void getCuttingEdge(int u, int parentEdgeId) {
low[u] = dfn[u] = ++ts;
for (int i = 0; i < edges[u].size(); ++i) {
int v = edges[u].get(i);
int id = edgesId[u].get(i);
if (dfn[v] == -1) {
getCuttingEdge(v, id);
low[u] = Math.min(low[u], low[v]);
if (low[v] > dfn[u]) {
ans.add(id);
}
} else if (id != parentEdgeId) {
low[u] = Math.min(low[u], dfn[v]);
}
}
}
}
注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。 边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
