首页 > 其他分享 >2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1, 同时还有一个数组 edges ,其中 edges[i] = [fromi, toi, weighti

2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1, 同时还有一个数组 edges ,其中 edges[i] = [fromi, toi, weighti

时间:2024-02-24 19:48:52浏览次数:21  
标签:02 24 info ei int edges var end

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) 函数向图中添加边,其中 ab 是集合编号,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) 连接边,构建大团子的图并找到桥。

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

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

  • 更新 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)
}

在这里插入图片描述

标签:02,24,info,ei,int,edges,var,end
From: https://www.cnblogs.com/moonfdd/p/18031458

相关文章

  • oracle指定控制文件启动 ORA-00205: error in identifying control file, check aler
    SQL>startupORACLEinstancestarted.TotalSystemGlobalArea1068937216bytesFixedSize2220200bytesVariableSize708841304bytesDatabaseBuffers352321536bytesRedoBuffers5554176bytesORA-00205:......
  • 52pj2024春节红包题-Android
    初级一小猫游戏,改一下判断将t.LOSE的值改为win,然后将casei.LOSE的代码段删掉,重新签名安装即可游戏结束会播放原神启动,播完会输出flag结果为flag{happy_new_year_2024}初级二flag是跟着签名走的,所以没法重新编译看代码可以看到是出金启动FlagActivity所以直接上obj......
  • P9562 [SDCPC2023] G-Matching 题解
    题目描述给定长度为\(n\)的整数序列\(a_1,a_2,\cdots,a_n\),我们将从该序列中构造出一张无向图\(G\)。具体来说,对于所有\(1\lei<j\len\),若\(i-j=a_i-a_j\),则\(G\)中将存在一条连接节点\(i\)与\(j\)的无向边,其边权为\((a_i+a_j)\)。求\(G\)的一个......
  • 2024牛客寒假算法基础集训营3
    2024牛客寒假算法基础集训营3A 智乃与瞩目狸猫、幸运水母、月宫龙虾题意给出若干组字符串,判断无视大小写,判断首字母是否相同思路如果首字母相同,则直接用\(==\)比较即可,如果首字母只有大小写的区别,则ASCII码值相差\(32\)代码/*******************************|Author:......
  • 2024/2/24
    要开学了ABC341A-Print341题意:输出n个10最后输出1#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn; cin>>n; for(inti=0;i<n;i++){ cout<<"10"; } cout<<1<<......
  • 推出新款H7-TOOL 2024版,同时发布新版固件V2.25(2024-02-24)
     H7-TOOL2024版介绍1、开模定制外壳,取消了侧面的IO接口,汇集到一个主端口(2*17P排针)。2、显示屏升级为2.8寸(分辨率320*240)。3、两个按键升级为4个按键:上键、下键,OK确认键和C取消键。4、预留一个电源开关按键,目前功能为HOME(返回初始界面)。5、新增4-20mA电流采集功能。6、......
  • 南外集训 2024.2.23 T3
    Kubic素质如此,如何国家队?有一个初始为空的序列,对其进行\(q\)次操作(强制在线)。操作分为两种:\(1\;x\)表示在序列末尾插入一个\(x\)。\(2\;x\)表示询问当前序列中长度等于\(x\)的区间的价值之和\(\bmod998244353\)。定义一个区间的价值为中前\(m\)大的数的乘......
  • 寒假集训总结(2024/2/24)
    先说考试t1:一眼线段树,但是,我非得加那个特判,导致在特判里的return0忘改了,直接把0以后的答案吃了,挂了75分(吐槽:大样例里为什么一个0也没有,服啦)。t2:一眼树上背包,第二眼1e9的数据范围,背包开不了一点。t3:没看出来是dp,打了个自己都不知道为啥的暴力,过了四个点,还不错。t4:这题真离谱,......
  • LOL通过召唤师名查战绩,突破战绩隐藏,2024-02-24有效
    importdatetimeimportrequestsasreqreq.packages.urllib3.disable_warnings()#执行下面步骤之前要先登录同区账号#需要查找的名字name='蓝火大魔王'#用管理员CMD执行wmicPROCESSWHEREname='LeagueClientUx.exe'GETcommandline#找到–remoting-auth-t......
  • 【C++】【OpenCV】Visual Studio 2022 配置OpenCV
    记录一下VisualStudio配置OpenCV过程以及出现的问题本机环境:1、Windows102、VisualStudio2022 配置步骤:1、下载OpenCV(Releases·opencv/opencv·GitHub)在GitHub上下载最新的版本 2、双击打开,然后选择路径后,点击Extract 3、等待提取完成后在VisualStudio中新......