图论|684.冗余连接 685. 冗余连接 II

2023-12-01 17:52
文章标签 连接 图论 ii 冗余 685 684

本文主要是介绍图论|684.冗余连接 685. 冗余连接 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

684.冗余连接
题目:树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。
题目链接:684.冗余连接
代码如下:
修改join函数

class Solution {public int[] father;public int[] findRedundantConnection(int[][] edges) {//构造并查集 过程中两个边根一样则删除int n=edges.length;father=new int[n+1];//初始化for(int i=1;i<=n;i++){father[i]=i;}int[] result=null;boolean flag;for(int j=0;j<edges.length;j++){flag=join(edges[j][0],edges[j][1]);if(flag==true){return new int[]{edges[j][0],edges[j][1]};}}return result;}public int find(int u){if(u==father[u]) return u;else return find(father[u]);}boolean join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return true;father[v] = u;return false;}
}

685. 冗余连接 II再分析
题目: 在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。
返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案
题目链接: 685. 冗余连接 II
解题思路:
先判断入度 删除入度为2的边的一条 判断删除后是不是树即可
再使用并查集判断是否有环(是否有冲突 此时的冲突一定是构成环)
如何使用并查集判断删除后是不是树
因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根,那么这条边添加上之后 这个图一定不是树了
如何使用并查集判断判断是否有环(有环时 附加的边指向根节点)
附加的边指向根节点,而且是在环路中的最后一条被访问到的边


class Solution {private static final int N = 1010;  // 如题:二维数组大小的在3到1000范围内private int[] father;public Solution() {father = new int[N];// 并查集初始化for (int i = 0; i < N; ++i) {father[i] = i;}}// 并查集里寻根的过程private int find(int u) {if(u == father[u]) {return u;}father[u] = find(father[u]);return father[u];}// 将v->u 这条边加入并查集private void join(int u, int v) {u = find(u);v = find(v);if (u == v) return ;father[v] = u;}// 判断 u 和 v是否找到同一个根,本题用不上private Boolean same(int u, int v) {u = find(u);v = find(v);return u == v;}/*** 初始化并查集*/private void initFather() {// 并查集初始化for (int i = 0; i < N; ++i) {father[i] = i;}}/*** 在有向图里找到删除的那条边,使其变成树* @param edges* @return 要删除的边*/private int[] getRemoveEdge(int[][] edges) {initFather();for(int i = 0; i < edges.length; i++) {if(same(edges[i][0], edges[i][1])) { // 构成有向环了,就是要删除的边return edges[i];}join(edges[i][0], edges[i][1]);}return null;}/*** 删一条边之后判断是不是树* @param edges* @param deleteEdge 要删除的边* @return  true: 是树, false: 不是树*/private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge){initFather();for(int i = 0; i < edges.length; i++){if(i == deleteEdge) continue;if(same(edges[i][0], edges[i][1])) { // 构成有向环了,一定不是树return false;}join(edges[i][0], edges[i][1]);}return true;}public int[] findRedundantDirectedConnection(int[][] edges) {int[] inDegree = new int[N];for(int i = 0; i < edges.length; i++){// 入度inDegree[ edges[i][1] ] += 1;}// 找入度为2的节点所对应的边,注意要倒序,因为优先返回最后出现在二维数组中的答案ArrayList<Integer> twoDegree = new ArrayList<Integer>();for(int i = edges.length - 1; i >= 0; i--){if(inDegree[edges[i][1]] == 2) {twoDegree.add(i);}}// 处理图中情况1 和 情况2// 如果有入度为2的节点,那么一定是两条边里删一个,看删哪个可以构成树if(!twoDegree.isEmpty()){if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {return edges[ twoDegree.get(0)];}return edges[ twoDegree.get(1)];}// 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回就可以了return getRemoveEdge(edges);}
}

这篇关于图论|684.冗余连接 685. 冗余连接 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/442113

相关文章

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

Java 连接Sql sever 2008

Java 连接Sql sever 2008 /Sql sever 2008 R2 import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement; public class TestJDBC

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

【Go】go连接clickhouse使用TCP协议

离开你是傻是对是错 是看破是软弱 这结果是爱是恨或者是什么 如果是种解脱 怎么会还有眷恋在我心窝 那么爱你为什么                      🎵 黄品源/莫文蔚《那么爱你为什么》 package mainimport ("context""fmt""log""time""github.com/ClickHouse/clickhouse-go/v2")func main(

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

nginx长连接的问题

转自: http://www.360doc.com/content/12/1108/17/1073512_246644318.shtml

NGINX轻松管理10万长连接 --- 基于2GB内存的CentOS 6.5 x86-64

转自:http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=190176&id=4234854 一 前言 当管理大量连接时,特别是只有少量活跃连接,NGINX有比较好的CPU和RAM利用率,如今是多终端保持在线的时代,更能让NGINX发挥这个优点。本文做一个简单测试,NGINX在一个普通PC虚拟机上维护100k的HTTP

TL-Tomcat中长连接的底层源码原理实现

长连接:浏览器告诉tomcat不要将请求关掉。  如果不是长连接,tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。