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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120  // @Title: 找到最小生成树里的关键边和伪关键边 (Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree) // @Author: 15816537946@163.com // @Date: 2021-01-21 21:49:37 // @Runtime: 8 ms // @Memory: 4.3 MB type unionFind struct { parent, size []int } func newUnionFind(n int) *unionFind { parent := make([]int, n) size := make([]int, n) for i := range parent { parent[i] = i size[i] = 1 } return &unionFind{parent, size} } func (uf *unionFind) find(x int) int { if uf.parent[x] != x { uf.parent[x] = uf.find(uf.parent[x]) } return uf.parent[x] } func (uf *unionFind) union(x, y int) bool { fx, fy := uf.find(x), uf.find(y) if fx == fy { return false } if uf.size[fx] < uf.size[fy] { fx, fy = fy, fx } uf.size[fx] += uf.size[fy] uf.parent[fy] = fx return true } func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int { m := len(edges) edgeType := make([]int, m) // -1：不在最小生成树中；0：伪关键边；1：关键边 for i, e := range edges { edges[i] = append(e, i) } sort.Slice(edges, func(i, j int) bool { return edges[i][2] < edges[j][2] }) type neighbor struct{ to, edgeID int } graph := make([][]neighbor, n) dfn := make([]int, n) // 遍历到该顶点时的时间戳 timestamp := 0 var tarjan func(int, int) int tarjan = func(v, pid int) int { timestamp++ dfn[v] = timestamp lowV := timestamp for _, e := range graph[v] { if w := e.to; dfn[w] == 0 { lowW := tarjan(w, e.edgeID) if lowW > dfn[v] { edgeType[e.edgeID] = 1 } lowV = min(lowV, lowW) } else if e.edgeID != pid { lowV = min(lowV, dfn[w]) } } return lowV } uf := newUnionFind(n) for i := 0; i < m; { vs := []int{} // 将权值相同的边分为一组，建图，然后用 Tarjan 算法找桥边 for weight := edges[i][2]; i < m && edges[i][2] == weight; i++ { e := edges[i] v, w, edgeID := uf.find(e[0]), uf.find(e[1]), e[3] if v != w { graph[v] = append(graph[v], neighbor{w, edgeID}) graph[w] = append(graph[w], neighbor{v, edgeID}) vs = append(vs, v, w) // 记录图中顶点 } else { edgeType[edgeID] = -1 } } for _, v := range vs { if dfn[v] == 0 { tarjan(v, -1) } } // 合并顶点、重置数据 for j := 0; j < len(vs); j += 2 { v, w := vs[j], vs[j+1] uf.union(v, w) graph[v] = nil graph[w] = nil dfn[v] = 0 dfn[w] = 0 } } var keyEdges, pseudokeyEdges []int for i, tp := range edgeType { if tp == 0 { pseudokeyEdges = append(pseudokeyEdges, i) } else if tp == 1 { keyEdges = append(keyEdges, i) } } return [][]int{keyEdges, pseudokeyEdges} } func min(a, b int) int { if a < b { return a } return b }