冗余连接2 hard题 代随C#写法

此题在卡码网109与力扣685题亦有记载  有一说一C#写法我没咋搞懂 就看明白了思路  这里贴一个答案待后续我醒悟了再来看罢   

难就难在对整体数据结构classUnion(并查集)的理解不熟并且 对于输入输出这个迭代过程理解上也比较吃力

109. 冗余连接II

题目描述

有一种有向树,该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图: 

现在有一个有向图,有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图:

输入一个有向图,该图由一个有着 n 个节点(节点编号 从 1 到 n),n 条边,请返回一条可以删除的边,使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N,表示有向图中节点和边的个数。 

后续 N 行,每行输入两个整数 s 和 t,代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边,若有多条边可以删除,请输出标准输入中最后出现的一条边。

输入示例
3
1 2
1 3
2 3
输出示例
2 3
提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树,所以输出 2 3

数据范围:

1 <= N <= 1000.

思路:

    //三种情况  情况一:如果我们找到入度为2的点,那么删一条指向该节点的边就行了

    //入度为2 还有一种情况,情况二,只能删特定的一条边 ,如果发现入度为2的节点,我们需要判断 删除哪一条边,删除后本图能成为有向树。如果是删哪个都可以,优先删顺序靠后的边。

    //情况三: 如果没有入度为2的点,说明 图中有环了(注意是有向环)解决方法:删掉构成环的边就可以了

    //具体方法:前两种入度为2的情况,一定是删除指向入度为2的节点的两条边其中的一条,如果删了一条,判断这个图是一个树,那么这条边就是答案。同时注意要从后向前遍历,因为如果两条边删哪一条都可以成为树,就删最后那一条

    //明确没有入度为2的情况,那么一定有向环,找到构成环的边就是要删除的边。

    //解决本题要实现两个最为关键的函数:

//isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树

//getRemoveEdge() 确定图中一定有了有向环,那么要找到需要删除的那条边

具体代码:

using System;
using System.Collections.Generic;

class Program
{
    static int n;
    static int[] father = new int[1001]; // 并查集的父节点数组
    static List<Tuple<int, int>> edges = new List<Tuple<int, int>>(); // 边的列表
    static int[] inDegree; // 记录节点入度

    // 并查集初始化
    static void Init()
    {
        for (int i = 1; i <= n; ++i)
        {
            father[i] = i;
        }
    }

    // 并查集里寻根的过程
    static int Find(int u)
    {
        if (u == father[u])
            return u;
        return father[u] = Find(father[u]);
    }

    // 将v->u 这条边加入并查集
    static void Join(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if (u != v)
        {
            father[v] = u;
        }
    }

    // 判断u和v是否在同一个集合中
    static bool Same(int u, int v)
    {
        return Find(u) == Find(v);
    }

    // 在有向图里找到删除的那条边,使其变成树
    static void GetRemoveEdge(List<Tuple<int, int>> edges)
    {
        Init(); // 初始化并查集
        foreach (var edge in edges)
        {
            int u = edge.Item1;
            int v = edge.Item2;

            if (Same(u, v)) // 构成有向环了,就是要删除的边
            {
                Console.WriteLine($"{u} {v}");
                return;
            }
            else
            {
                Join(u, v);
            }
        }
    }

    // 删一条边之后判断是不是树
    static bool IsTreeAfterRemoveEdge(List<Tuple<int, int>> edges, int deleteEdge)
    {
        Init(); // 初始化并查集
        for (int i = 0; i < n; i++)
        {
            if (i == deleteEdge) continue;
            int u = edges[i].Item1;
            int v = edges[i].Item2;

            if (Same(u, v)) // 构成有向环了,一定不是树
            {
                return false;
            }
            Join(u, v);
        }
        return true;
    }

    static void Main()
    {
        // 读入数据
        n = int.Parse(Console.ReadLine());
        inDegree = new int[n + 1]; // 记录节点入度
        for (int i = 0; i < n; i++)
        {
            string[] input = Console.ReadLine().Split();
            int s = int.Parse(input[0]);
            int t = int.Parse(input[1]);

            inDegree[t]++;
            edges.Add(new Tuple<int, int>(s, t));
        }

        List<int> vec = new List<int>(); // 记录入度为2的边
        // 找入度为2的节点所对应的边,注意要倒序,因为优先删除最后出现的一条边
        for (int i = n - 1; i >= 0; i--)
        {
            if (inDegree[edges[i].Item2] == 2)
            {
                vec.Add(i);
            }
        }

        // 情况一、情况二
        if (vec.Count > 0)
        {
            // 放在vec里的边已经按照倒叙放的,所以这里就优先删vec[0]这条边
            if (IsTreeAfterRemoveEdge(edges, vec[0]))
            {
                Console.WriteLine($"{edges[vec[0]].Item1} {edges[vec[0]].Item2}");
            }
            else
            {
                Console.WriteLine($"{edges[vec[1]].Item1} {edges[vec[1]].Item2}");
            }
            return;
        }

        // 处理情况三
        // 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回就可以了
        GetRemoveEdge(edges);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/14024.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

MySQL:CRUD

MySQL表的增删改查&#xff08;操作的是表中的记录&#xff09; CRUD(增删改查) C-Create新增R-Retrieve检查&#xff0c;查询U-Update更新D-Delete删除 新增&#xff08;Create&#xff09; 语法&#xff1a; 单行数据全列插入 insert into 表名[字段一&#xff0c;字段…

【stable diffusion部署】手把手教你从0基础入门Stable Diffusion

前言 在开始学之前&#xff0c;我想提前说一下&#xff0c;我所理解的AI绘画的本质&#xff0c;就是手替&#xff0c;人提出方案&#xff0c;AI帮你完成具体的作画过程。 写这篇文章的初衷&#xff0c;网上的Stable Diffusion教程太多了&#xff0c;但是我真正去学的时候发现…

前端单元测试框架 引入说明

1. 背景&#xff1a; 2. 如何选择&#xff1a; 2.1. 流行框架 Jest&#xff1a;由Facebook开源的JavaScript测试框架&#xff0c;应用于脸书系以及 ReactJs 系Mocha&#xff1a;适用于 NodeJs 和 浏览器、简易、灵活、有趣的JavaScript 测试框架Jasmine&#xff1a;BDD&#…

有效提升网站流量的SEO技巧分享

内容概要 在数字时代&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;已经成为提升网站曝光度和吸引访问者的重要工具。SEO的核心目标是通过优化网站的各个方面&#xff0c;提高在搜索引擎结果页面上的排名&#xff0c;从而获得更多的自然流量。有效的SEO策略能够让您在激…

MacBook不额外安装软件,怎样投屏到安卓手机上?

提起iPhone或MacBook的投屏&#xff0c;人们总会想到airplay功能。但离开了苹果生态&#xff0c;其他品牌的手机电脑就未必配备airplay功能了。 如果想要将MacBook的电脑屏幕共享到安卓手机或平板上&#xff0c;到底要怎样做&#xff1f;需要安装什么软件吗&#xff1f; 不需要…

自定义面板,高效的游戏性能分析利器

为了更有效地聚焦并解决性能问题&#xff0c;UWA报告采用了分模块监控策略&#xff0c;确保每个模块独立成章&#xff0c;各司其职。然而&#xff0c;随着对性能分析需求的不断升级&#xff0c;我们已经意识到&#xff0c;在深入分析某些跨模块的性能瓶颈或优化点时&#xff0c…

2024第四次随堂测验参考答案

从第四次开始答案会以c语言提供&#xff0c;自行了解&#xff0c;学习 6-1 报数 报数游戏是这样的&#xff1a;有n个人围成一圈&#xff0c;按顺序从1到n编好号。从第一个人开始报数&#xff0c;报到m&#xff08;<n&#xff09;的人退出圈子&#xff1b;下一个人从1开始报…

CTF杂项基本题目思路(图片文件隐写-压缩文件-流量取证)

一、文件隐写 1.当遇到文件类型未知的文件时怎么办&#xff1f; ①linux系统可以使用file命令查看文件的类型&#xff0c;格式&#xff1a;file 文件名 ②使用winhex或者010editor查看文件头&#xff0c;从而判断文件的类型&#xff0c;①中file命令的本质也是查看文件的文件…

sa-token使用及与spring-security的对比

sa-token相关资料地址 官网: https://sa-token.cc/ gitee: https://gitee.com/dromara/sa-token github: https://github.com/dromara/sa-token 快速开始: https://sa-token.cc/doc.html#/ sa-token典型应用 这里我直接拿SpringBoot_v2&#xff08;springboot的开源后台脚手…

MySQL:left join后用on与where的区别

一、前言 前几天项目中&#xff0c;写SQL时本想通过 A left B join on and 后面的条件来使查出的两条记录变成一条&#xff0c;奈何发现还是有两条。在此记录一下&#xff0c;on与where的区别。 二、ON 原始数据展示 SELECT t1.*,t2.* FROM t_test_staff t1 left join t_te…

ANX9833FN-AA-R ANX9833 ANALOGIX QFN48 VGA视频转换器件

ANX9833概述:ANX9833是VGA显示接口适配器集成电路设计一个显示端口1.2/1.1源连接到一个VGA显示。与芯片上的单片机和记忆,ANX9833不需要任何外部配置或设置。它自动引导VGA显示接口适配器的输出,有效地处理所有类型的遗产显示器、投影仪,和电视。ANX9833提供Gbps带宽在两车道到…

2025全平台短剧系统 : 快手、抖音、微信全覆盖

之前&#xff0c;我曾详细阐述过公司短剧系统的一些功能&#xff0c;它们共同构建了一个全面、高效的短剧制作与运营平台。这些功能&#xff0c;无论是媒资管理、剧场设定&#xff0c;还是后期运营&#xff0c;都是经过深思熟虑、精心设计的&#xff0c;是一个成熟的短剧系统所…

机圈白刃战,vivo聚势成风

金秋十月&#xff0c;国产手机市场进入了空前激烈的竞争局势&#xff0c;几乎每天都有发布会&#xff0c;甚至隔段时间就有新机话题登上热搜。网友戏称&#xff0c;发布会密度高到“工作日都不够用了”。 10月14日&#xff0c;vivo X200系列率先登场&#xff0c;拉开了国产旗舰…

scp 或 ssh 报错no matching host key type found. Their offer: ssh-rsa 解决方案

报错如下&#xff1a; 解决方案&#xff1a; 在 scp 或 ssh 命令后面增加参数&#xff1a; -o HostKeyAlgorithmsssh-rsa 可以解决此问题&#xff0c; scp格式如下&#xff1a; scp -o HostKeyAlgorithmsssh-rsa [local_file_path] [user][hosts]:[remote_path]

ElasticSearch概述

ElasticSearch概述 Elaticsearch&#xff0c;简称为es&#xff0c; es是一个开源的高扩展的分布式全文检索引擎&#xff0c;它可以近乎实时的存储、检索数据&#xff1b;本身扩展性很好&#xff0c;可以扩展到上百台服务器&#xff0c;处理PB级别的数据。es也使用Java开发并使…

一文彻底了解UDHCP源码核心☝️

&#x1f344;参考学习: udhcp源码剖析&#xff08;一&#xff09;——DHCP服务器和客户端的工作流程_udhcpc源码v1.29.2-CSDN博客 前言介绍 本文深入探讨了DHCP服务器和客户端的工作流程&#xff0c;以udhcp为例&#xff0c;详细阐述了udhcpd&#xff08;服务器&#xff09;…

开启鸿蒙开发之旅:静态页面搭建

写在前面 了解了一些常用的系统组件及其属性之后&#xff0c;我准备开始搭建我第一个页面&#xff0c;本次鸿蒙Next初体验我准备模仿这款“提醒事项”APP&#xff0c;从页面搭建到基本功能实现。今天从入口页开始&#xff1a; 布局思路 整体结构 从该页面的整体布局结构来看&…

C++20 STL CookBook 7 Containers(II)

让vector在插入删除的时候仍然保证是有序的 首先&#xff0c;STL的确提供了一种办法来检查我们的目标容器是不是有序的&#xff1a;std::is_sorted - cppreference.com&#xff0c;也就是std::is_sorted。我们当然可以这样做&#xff1a; #include <iostream> #include…

二叉树搜索树(下)

二叉树搜索树&#xff08;下&#xff09; 二叉搜索树key和key/value使用场景 key搜索场景 只有key作为关键码&#xff0c;结构中只需要存储key即可&#xff0c;关键码即为需要搜索到的值&#xff0c;搜索场景只需要判断 key在不在。key的搜索场景实现的二叉树搜索树支持增删查…

人力资源招聘系统-提升招聘效率与质量的关键工具

在当今这个竞争激烈的商业环境中&#xff0c;企业要想在市场中立于不败之地&#xff0c;关键在于拥有高素质的人才队伍。然而&#xff0c;传统的招聘方式往往效率低下&#xff0c;难以精准匹配企业需求与人才特质&#xff0c;这无疑给企业的发展带来了不小的挑战。 随着科技的飞…