首页 > 其他分享 >代码随想录day55 || 图论5

代码随想录day55 || 图论5

时间:2024-09-09 13:51:27浏览次数:9  
标签:图论 return int 随想录 father edges find edge day55

并查集

image

197 图中是否存在有效路径

var father []int
func validPath(n int, edges [][]int, source int, destination int) bool {
	// 使用并查集算法,涉及到的操作,包括init,find, issample,join
	father = make([]int, n)
	for i, _ := range father {  // init
		father[i] = i
	}

	// insert
	for _, edge := range edges {
		join(edge[0], edge[1])
	}

	return isSame(source, destination)
}

func find(u int) int {
	if u == father[u] { // 只有根节点的父节点等于自己
		return u
	}
	res := find(father[u]) // res 保存的是多次递归之后最终的根
	father[u] = res // u是查询的节点,father[u] 含义是u的父节点,father[u] = res,代表将u的父节点指向根,这里操作就是路由压缩
	return res
}

func join(u, v int) {
	// 先拿到u,v的根节点,不能直接对比find(u) == find(v), 因为下面还有赋值操作
	u = find(u)
	v = find(v)
	if u == v {
		return
	}
	father[u] = v
}

func isSame(u, v int) bool {
	if find(u) == find(v) {
		return true
	}
	return false
}

684 冗余连接


var father []int
var res []int
func findRedundantConnection(edges [][]int) []int {
	// 考察并查集知识,什么叫做冗余连接呢?就是并查集中出现的路径压缩,2->1, 3->1, 3->2==>2的根是1,3的根也是1,已经再同一集合, 这就是冗余连接
	// 所以本题思路就是join过程如果出现了已经在同一个集合中,那么此时再插入这条边,就会出现环

	// init
	res = []int{}
	father = make([]int, len(edges))
	for i, _ := range father{
		father[i] = i
	}

	for _, edge := range edges {
		join(edge[0], edge[1])
	}

	return res
}


func find(u int) int {
	if u == father[u] {
		return u
	}
	r := find(father[u])
	father[u] = r
	return r
}

func join(u ,v int ){ // 加入u->v 这条边
	fu := find(u-1)
	fv := find(v-1)
	if fu == fv {  // 已经在集合中
		res = []int{u, v}
		return
	}
	father[fu] = fv
}

冗余连接II

image

var father []int
func findRedundantDirectedConnection(edges [][]int) []int {
	// 需要针对两种大情况,三种小情况分别处理,两大分别是是否出现节点入度为2
	// 如果没有入度2节点,说明出现了环,并查集删除边即可
	// 如果出现入度2节点,1,两条边都可以删除,那么就删除后出现的边
	//                 2, 只有一条边能够保持删除后还是树,那就删除此边
	var nodeCount = make(map[int][][]int, len(edges))
	var node [][]int // 保存可能出现的入度2的两条边, 长度只能是0 或者 2
	father = make([]int, len(edges))
	for i ,_ := range edges{
		father[i] = i
	}

	// 判断是否有入度2的节点
	for _, edge := range edges {
		nodeCount[edge[1]] = append(nodeCount[edge[1]], edge)
		if len(nodeCount[edge[1]]) == 2{
			node = nodeCount[edge[1]]
		}
	}

	if len(node) == 0 { // 出现了环,没有入度为2的节点
		for _, edge := range edges {
			if same(edge[0], edge[1]) { // 出现了同时在集合中,这时这条要加入的边就是成环的边
				return edge
			}else {
				join(edge[0], edge[1])
			}
		}
	}else { // 出现入度为2节点
		// 判断一下删除之后是否还能够成树,node是顺序加入的两条边,所以遍历要倒叙,优先删除的是后面插入的边

		if checkTreeAfterRemove(edges, node[1]) {
			return node[1]
		}
		return node[0]
	}
	return []int{}
}

func find(u int) int {
	if u == father[u] {
		return u
	}
	r := find(father[u])
	father[u] = find(father[u])
	return r
}

func join(u, v int) {
	fu := find(u-1)
	fv := find(v-1)
	if fu == fv{
		return
	}
	father[fv] = fu
}

func same(u,v int )bool {
	if find(u-1) == find(v-1){
		return true
	}
	return false
}

func checkTreeAfterRemove(edges [][]int, remove []int)bool {
	// 思考一下原理,如果对于只能删除一条边的情况,错删除会导致出现一个单独节点,一个环,所以原理就是判断不加入这条边是否有环
	for _, edge := range edges {
		if edge[0] == remove[0] && edge[1] == remove[1] {
			continue
		}
		if same(edge[0], edge[1]) { // 出现了同时在集合中,这时这条要加入的边就是成环的边
			return false // 出现了环就是图,不是树了
		}else {
			join(edge[0], edge[1])
		}
	}
	return true
}

标签:图论,return,int,随想录,father,edges,find,edge,day55
From: https://www.cnblogs.com/zhougongjin55/p/18404404

相关文章

  • 代码随想录训练营 Day53打卡 图论part04 110. 字符串接龙 105. 有向图的完全可达性 10
    代码随想录训练营Day53打卡图论part04一、卡码110.字符串接龙本题与力扣127题是一样的,所以这里使用力扣127题。字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->…->sk:    每一对相邻的单词只......
  • 代码随想录算法训练营,9月7日 | 150. 逆波兰表达式求值,239. 滑动窗口最大值,347.前 K 个
    150.逆波兰表达式求值题目链接:150.逆波兰表达式求值文档讲解︰代码随想录(programmercarl.com)视频讲解︰逆波兰表达式求值日期:2024-09-07想法:用栈解决,遇到运算符取前两个数字计算(表达式总是成立的,不用做额外的判定)Java代码如下:classSolution{publicintevalRPN(Stri......
  • 图论篇--代码随想录算法训练营第五十三天打卡| 110. 字符串接龙,105.有向图的完全可达
    110.字符串接龙题目链接:110.字符串接龙题目描述:字典strList中从字符串beginStr和endStr的转换序列是一个按下述规格形成的序列: 序列中第一个字符串是beginStr。序列中最后一个字符串是endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典......
  • 代码随想录算法训练营第九天 | Javascript | 力扣Leetcode | 手撕KMP的一天 | 28. 找
    目录前言简介题目链接:28.找出字符串中第一个匹配项的下标题目链接:459.重复的子字符串前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄弱。......
  • 【代码随想录Day10】栈与队列Part01
    232.用栈实现队列题目链接/文章讲解/视频讲解:用栈实现队列classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=newStack<>();}publicvoidpush(int......
  • 【代码随想录Day9】字符串Part02
    151.翻转字符串里的单词解题思路如下:移除多余空格将整个字符串反转将每个单词反转举个例子,源字符串为:"theskyisblue"移除多余空格:"theskyisblue"字符串反转:"eulbsiykseht"单词反转:"blueisskythe"题目链接/文章讲解/视频讲解:代码随想录publicclassS......
  • 代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II
    代码随想录刷题day25丨491.递增子序列,46.全排列,47.全排列II1.题目1.1递增子序列题目链接:491.非递减子序列-力扣(LeetCode)视频讲解:回溯算法精讲,树层去重与树枝去重|LeetCode:491.递增子序列_哔哩哔哩_bilibili文档讲解:https://programmercarl.com/0491.%E9%80......
  • 第十一章 图论 Part4
    目录任务127.单词接龙思路Kama105.有向图的完全可达性思路463.岛屿的周长思路任务127.单词接龙字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->...->sk:每一对相邻的单词只差一个字母。对于1<=i<=......
  • 图论板子
    Primtypedefpair<int,int>P;intprim(){intans=0,cnt=0;priority_queue<P,vector<P>,greater<P>>q;fill(d+1,d+n+1,INF);d[1]=0;q.push(P(d[1],1));while(!q.empty()&&cnt<......
  • 代码随想录day 53 || 图论4
    字符串接龙varqueue*list.ListvarvisitMapmap[string]boolfuncmain(){ varcountint fmt.Scanf("%d",&count) varstartStr,endStrstring fmt.Scanf("%s%s",&startStr,&endStr) varstrList=make([]string,count) fo......