2024-02-24：用go语言，给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1， 同时还有一个数组 edges

2024-02-24：用go语言，给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1，

同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti]，

表示在 fromi 和 toi 节点之间有一条带权无向边，

最小生成树 (MST) 是给定图中边的一个子集，

它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。

如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边，

伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

输入：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]]。

答案2024-02-24：

来自左程云。

灵捷3.5

大体过程如下：

1.定义并查集和辅助数组：首先定义并查集的数据结构，包括父节点数组father、节点大小数组size、辅助数组help，以及集合数量sets。还需要定义边的状态记录数组status，其中status[ei]记录第ei条边的状态。

2.初始化并查集：使用buildUnionSet(n)函数初始化并查集，将每个节点自成一个集合。

3.构建边数组：使用buildEdges(e)函数将输入的边数组e转换成包含边信息的二维数组edges，并按照权值从小到大进行排序。

4.建立图：根据集合编号建立图的相关数据结构，包括链式前向星建图。定义头指针数组head、边信息数组info、下一条边指针数组next，以及边数量edgeSize。使用buildGraph(k)函数初始化这些数组。

5.添加边：使用addEdge(a, b, ei)函数向图中添加边，其中a和b是集合编号，ei是边的索引。

6.找桥：使用 Tarjan 算法，利用深度优先搜索找到所有的桥。具体实现在函数tarjan(init, cur, father, ei)中，其中init是起始节点，cur是当前节点，father是当前节点的父节点，ei是当前边的索引。

7.寻找关键边和伪关键边：通过遍历边数组edges，逐个加入到最小生成树中，并利用并查集判断是否形成环。在每次加入边的过程中，记录是否是关键边或伪关键边。具体过程如下：

• 初始化起始索引start = 0。

• 当并查集的集合数量不为 1 时，继续循环。

• 确定结束索引end，使得edges[start][3] != edges[end][3]或者end == m。

• 调用connect(start, end)连接边，构建大团子的图并找到桥。

• 遍历start到end的边，根据边的状态记录到关键边或伪关键边的数组中。

• 合并集合，更新并查集。

• 更新start = end，继续下一轮循环。

8.返回结果：将关键边和伪关键边的数组返回作为结果。

综上所述，总的时间复杂度为 O(m^2 * α(n))，其中 m 是边的数量，n 是节点的数量，α 是阿克曼函数的反函数。总的额外空间复杂度为 O(m + n)。

go完整代码如下：

package main

import (

"fmt"

"sort"

)

const MAXN = 101

const MAXM = 201

// 边状态的记录

// status[ei] = 0，代表ei这个边既不是关键边也不是伪关键边

// status[ei] = 1，代表ei这个边是伪关键边

// status[ei] = 2，代表ei这个边是关键边

var status [MAXM]int

// 并查集相关

var father [MAXN]int

var size [MAXN]int

var help [MAXN]int

var sets int

// 并查集初始化

func buildUnionSet(n int) {

for i := 0; i < n; i++ {

father[i] = i

size[i] = 1

}

sets = n

}

// 并查集向上找代表节点

func find(i int) int {

r := 0

for i != father[i] {

help[r] = i

i = father[i]

r++

}

for r > 0 {

r--

father[help[r]] = i

}

return i

}

// 并查集合并集合

func union(i, j int) {

fi := find(i)

fj := find(j)

if fi != fj {

if size[fi] >= size[fj] {

father[fj] = fi

size[fi] += size[fj]

} else {

father[fi] = fj

size[fj] += size[fi]

}

sets--

}

}

// 边相关

var edges [MAXM][4]int

var m int

func buildEdges(e [][]int) {

for i := 0; i < m; i++ {

edges[i][0] = i

edges[i][1] = e[i][0]

edges[i][2] = e[i][1]

edges[i][3] = e[i][2]

}

sort.Slice(edges[:m], func(i, j int) bool {

return edges[i][3] < edges[j][3]

})

}

// 通过集合编号建图相关

// 链式前向星建图

// 为啥用这玩意儿建图？没啥，就是想秀

var head [MAXN]int

var info [MAXM][3]int

var next [MAXM]int

var edgeSize int

func buildGraph(k int) {

for i := 0; i < k; i++ {

head[i] = -1

edgeSize = 0

}

}

func addEdge(a, b, ei int) {

next[edgeSize] = head[a]

info[edgeSize][0] = ei

info[edgeSize][1] = a

info[edgeSize][2] = b

head[a] = edgeSize

edgeSize++

}

// 哈希表相关

// 一个集合，给一个编号

var id [MAXN]int

// 找桥相关

var dfn [MAXN]int

var low [MAXN]int

var cnt int

func findBridge(k int) {

for i := 0; i < k; i++ {

dfn[i] = 0

low[i] = 0

}

cnt = 0

for init := 0; init < k; init++ {

if dfn[init] == 0 {

tarjan(init, init, -1, -1)

}

}

}

func tarjan(init, cur, father, ei int) {

cnt++

dfn[cur] = cnt

low[cur] = cnt

for i := head[cur]; i != -1; i = next[i] {

edgei := info[i][0]

nodei := info[i][2]

if nodei != father {

if dfn[nodei] == 0 {

tarjan(init, nodei, cur, edgei)

low[cur] = min(low[cur], low[nodei])

} else {

low[cur] = min(low[cur], dfn[nodei])

}

}

}

if low[cur] == dfn[cur] && cur != init {

status[ei] = 2

}

}

func findCriticalAndPseudoCriticalEdges(n int, e [][]int) [][]int {

m = len(e)

buildUnionSet(n)

buildEdges(e)

var bridge []int

var pseudo []int

start := 0

for sets != 1 {

end := start + 1

for end < m && edges[start][3] == edges[end][3] {

end++

}

connect(start, end)

for i := start; i < end; i++ {

ei := edges[i][0]

if status[ei] == 2 {

bridge = append(bridge, ei)

} else if status[ei] == 1 {

pseudo = append(pseudo, ei)

}

union(edges[i][1], edges[i][2])

}

start = end

}

return [][]int{bridge, pseudo}

}

// 大团子，一个集合，缩成一个点

// 当前的边，[start...end)

// 做图！大团子的图，找桥！

func connect(start, end int) {

for i := start; i < end; i++ {

id[find(edges[i][1])] = -1

id[find(edges[i][2])] = -1

}

k := 0

for i := start; i < end; i++ {

if id[find(edges[i][1])] == -1 {

id[find(edges[i][1])] = k

k++

}

if id[find(edges[i][2])] == -1 {

id[find(edges[i][2])] = k

k++

}

}

buildGraph(k)

for i := start; i < end; i++ {

index := edges[i][0]

a := id[find(edges[i][1])]

b := id[find(edges[i][2])]

if a != b {

status[index] = 1

addEdge(a, b, index)

addEdge(b, a, index)

}

}

findBridge(k)

sort.Slice(info[:edgeSize], func(i, j int) bool {

if info[i][1] != info[j][1] {

return info[i][1] < info[j][1]

}

return info[i][2] < info[j][2]

})

right, left := 0, 0

for left < edgeSize {

right = left + 1

for right < edgeSize && info[left][1] == info[right][1] {

right++

}

for i := left + 1; i < right; i++ {

if info[i][2] == info[i-1][2] {

status[info[i][0]] = 1

status[info[i-1][0]] = 1

}

}

left = right

}

}

func min(a, b int) int {

if a < b {

return a

}

return b

}

func main() {

n := 5

edges := [][]int{{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}}

result := findCriticalAndPseudoCriticalEdges(n, edges)

fmt.Println(result)

}

在这里插入图片描述