首页 > 其他分享 >leetcode684冗余连接(模板题,理解背过就行)

leetcode684冗余连接(模板题,理解背过就行)

时间:2024-03-23 21:23:57浏览次数:26  
标签:map 连通 int 节点 edges 冗余 leetcode684 public 模板

leetcode684冗余连接(模板题,理解背过就行)

考了图的连通,笔试碰见了还好老底没忘,不然就尬住了,总结一下。

一、题目

树可以看成是一个连通且 无环无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edgesedges[i] = [ai, bi] 表示图中在 aibi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。

二、示例

image

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

image

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

三、提示

n == edges.length

3 <= n <= 1000

edges[i].length == 2

1 <= ai < bi <= edges.length

ai != bi

edges中无重复元素
给定的图是连通的

四、详解

package main;

/**
 * @author 芊嵛
 * @date 2024/3/22
 */
public class Test02 {
    public static void main(String[] args) {
        // 节点n
        int n = 5;
        // 边
        int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
        // 调用函数求结果
        System.out.print("[" + res(edges)[0] + "," + res(edges)[1] + "]");
    }

    public static int[] res(int[][] edges) {
//        定义连通的图,为的是下标从1开始所以+1
        int[] map = new int[edges.length + 1];
//        初始化自己给自己连通,自己到自己肯定是通的
        for (int i = 0; i < map.length; i++) {
            map[i] = i;
        }

        // 全部遍历看是否连通
        for (int i = 0; i < edges.length; i++) {
            // 如果连通代表不需要这个点可以删,多了就成环了
            if (connected(edges[i][0], edges[i][1], map)) {
                return new int[]{edges[i][0], edges[i][1]};
            } else {
                // 如果不连通把他们加入图中
                union(edges[i][0], edges[i][1], map);
            }
        }
        // 返回值在此题中无用
        return new int[0];
    }

    //    找到根节点
    public static int find(int n, int[] map) {
        while (map[n] != n) {
            map[n] = map[map[n]];
            n = map[n];
        }
        return map[n];
    }

    //    根据根节点判断是否连通
    public static boolean connected(int n, int m, int[] map) {
        // 如果两个点连通代表他们的根节点都相同
        return find(n, map) == find(m, map);
    }


    // 如果不连通,让他们加入图中
    public static void union(int n, int m, int[] map) {
        int f1 = find(n, map);
        int f2 = find(m, map);
        if (f1 == f2) {
            return;
        }
        map[f1] = f2;
    }

}

五、拓展

可以在试着求一下连通分量

标签:map,连通,int,节点,edges,冗余,leetcode684,public,模板
From: https://www.cnblogs.com/qy-blog/p/18091700

相关文章

  • 模板文件
    #!/usr/bin/python3#coding=utf-8importdatetimeimportsubprocessdefget_yesterday():date=datetime.date.today()returndate-datetime.timedelta(days=1)APP="AIS"defcheck_hdfs_path(path):try:subprocess.run([......
  • 4.1.2、类模板
    1、类模板的语法类模板的作用:建立一个通用类,类中的成员数据类型可以不具体指定,用一个虚拟的类型来代表。语法:template<typenameT>类解释:template---声明创建模板typename---表面其后面的符号是一种数据类型,可以用class代替T---通用的数据类型,名称可以替......
  • 抖音,剪映,TikTok,竖屏短视频转场pr模板视频素材
    120个叠加效果视频转场过渡素材,抖音,剪映,TikTok,短视频转场pr模板项目工程文件。效果:VHS、光效、胶片、霓虹灯闪光、X射线、信号、老电影等。适用软件:AdobePremierePro201812.0或更高版本。视频素材与大多数应用程序兼容:剪映、必剪、LumaFusion、CupCut、VN、InSho......
  • 【模板】单调队列 滑动窗口最值
    LuoguP1886滑动队列/单调队列有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 以求最小值为例f[i]表示以i结尾的窗口中的最小值f[i]=min(a[j]),i-k+1<=j<=i暴力算法O(n^2)......
  • 排序合集模板
    #include<bits/stdc++.h>usingnamespacestd;constintN=1005;inta[N];intt[N];intn;voidbubbleSort(inta[],intn){//冒泡排序://时间复杂度:O(n^2)//是否稳定:是 for(inti=n;i>1;i--){ for(intj=1;j<i;j++){ if(a[j]>a[j+1]){......
  • 常见算法模板
    常见算法快速排序#include<iostream>#include<algorithm>//快速排序voidqsort(inta[],intleft,intright){if(left>=right)return;inti=left-1,j=right+1;intx=a[left+right>>1];while(i<j){doi++;while(a[i]<x);doj--;while(a[j]>......
  • 台达变频通过Modbus转Profinet网关可以在环网冗余中使用
    Modbus转Profinet网关(XD-MDPN100)是一种能够实现Modbus协议与Profinet协议之间转换的设备。它支持ModbusRTU协议和Profinet协议还支持MRP环网冗余系统,,可以通过配置软件进行协议转换,使得原本只能使用Modbus协议的设备可以与使用Profinet协议的系统进行通信。下面以Modbus转Profi......
  • [C++提高编程](一):模板----函数模板
    目录函数模板作用函数模板的语法注意事项普通函数与函数模板的区别普通函数与函数模板的调用规则模板的局限性案例--通用数组选择排序从大到小模板是C++中泛型编程的基础,一个模板就是一个创建类或函数的蓝图或者公式。函数模板作用建立一个通用函数,其函数返回值类型......
  • C# 根据模板导出Excel
    ///<summary>///导出Excel(使用模板)///</summary>///<returns></returns>[HttpGet]publicIActionResultExportExcelByTemplate(){try{IWorkbookwb=null;vartemplate=Directory.GetCurrentDirectory()+@&q......
  • 【包远程安装运行】SpringBoot+Mysql实现的共享厨房平台+演示视频+开发文档(论文模板)
    今天发布的是由【猿来入此】的优秀学员独立做的一个基于springboot脚手架的共享厨房平台系统,该系统可以实现线上提前预约,线下使用。利用支付宝沙箱来作为支付方式,使该系统更切合实际的表现出实体店线下共享厨房的流程。该系统分为前台和后台。主要实现了除脚手架功能以外下......