冗余连接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.rhkb.cn/news/470656.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【QT】QSS

个人主页~ 一、QSS QSS可以说是拿了CSS的一部分过来用&#xff0c;是CSS的简化版本 1、基本语法 选择器 {属性名:属性值; }将界面上所有的QPushButton文本颜色都改为红色 QPushButton {color:red; }2、设置方式 &#xff08;1&#xff09;指定控件样式设置 在widget.cpp中…

java模拟键盘实现selenium上下左右键 table中的左右滚动条实现滚动

在这篇文章中&#xff0c;我们将学习如何使用Java编程语言模拟键盘输入&#xff0c;特别是模拟上下左右方向键的操作。这是一个很有趣的项目&#xff0c;尤其适合刚入行的开发者。我们将分步进行&#xff0c;接下来&#xff0c;我们会通过表格展示整个实现过程&#xff0c;然后…

JQuery封装的ajax

1. 注意&#xff1a; 首先要导jq的包json对象可以用 . 来调用keyjava只能给前端传页面&#xff0c;或者打印的内容String jsonstr json.toJSONString(resultJSON); //将对象转为JSON对象 Json格式和参数解释&#xff1a; <script src"js/jquery-1.10.2.min.js&quo…

文献解读-DNAscope: High accuracy small variant calling using machine learning

关键词&#xff1a;基准与方法研究&#xff1b;基因测序&#xff1b;变异检测&#xff1b; 文献简介 标题&#xff08;英文&#xff09;&#xff1a;DNAscope: High accuracy small variant calling using machine learning标题&#xff08;中文&#xff09;&#xff1a;DNAsc…

vue中如何关闭eslint检测?

ESLint作为一个用于JavaScript代码的验证工具&#xff0c;主要用于检查代码语法和编码规范。本文旨在指导那些希望在Vue.js项目中禁用ESLint验证功能的用户。对于需要这一操作的朋友&#xff0c;以下内容将提供参考。 vue中如何关闭eslint检测&#xff1f; 有了eslint的校验&…

用vscode编写verilog时,如何有信号定义提示、信号定义跳转(go to definition)、模块跳转这些功能

&#xff08;一&#xff09;安装插件SystemVerilog - Language Support 安装一个vscode插件即可&#xff0c;插件叫SystemVerilog - Language Support。虽然说另一个插件“Verilog-HDL/SystemVerilog/Bluespec SystemVerilog”也有信号提示及定义跳转功能&#xff0c;但它只能提…

️️一篇快速上手 AJAX 异步前后端交互

AJAX 1. AJAX1.1 AJAX 简介1.2 AJAX 优缺点1.3 AJAX 前后端准备1.4 AJAX 请求基本操作1.5 AJAX 发送 POST 请求1.6 设置请求头1.7 响应 JSON 数据1.8 AJAX 请求超时与网络异常处理1.9 取消请求1.10 Fetch 发送 Ajax 请求 2. jQuery-Ajax2.1 jQuery 发送 Ajax 请求&#xff08;G…

❤React-React 组件通讯

❤ React 组件通讯 组件通讯将教我们的内容&#xff1a; 能够使用道具接收数据W能够实现父子组件之间的通讯能够实现兄弟组件之间的通讯能够给组件添加道具校验能够说出生命周期常用的钩子函数能够知道高阶组件的作用 1、 组件通讯介绍 组件是独立且封闭的单元&#xff0c;…

【初阶数据结构与算法】链表刷题之移除链表元素、反转链表、找中间节点、合并有序链表、链表的回文结构

文章目录 一、移除链表元素思路一思路二 二、合并两个有序链表思路&#xff1a;优化&#xff1a; 三、反转链表思路一思路二 四、链表的中间节点思路一思路二 五、综合应用之链表的回文结构思路一&#xff1a;思路二&#xff1a; 一、移除链表元素 题目链接&#xff1a;https:…

POI实现根据PPTX模板渲染PPT

目录 1、前言 2、了解pptx文件结构 3、POI组件 3.1、引入依赖 3.2、常见的类 3.3、实现原理 3.4、关键代码片段 3.4.1、获取ppt实例 3.4.2、获取每页幻灯片 3.4.3、循环遍历幻灯片处理 3.4.3.1、文本 3.4.3.2、饼图 3.4.3.3、柱状图 3.4.3.4、表格 3.4.3.5、本地…

计算机毕业设计Python+Neo4j知识图谱医疗问答系统 大模型 机器学习 深度学习 人工智能 大数据毕业设计 Python爬虫 Python毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

【机器学习】机器学习中用到的高等数学知识-2.概率论与统计 (Probability and Statistics)

概率分布&#xff1a;理解数据的分布特征&#xff08;如正态分布、伯努利分布、均匀分布等&#xff09;。期望和方差&#xff1a;描述随机变量的中心位置和离散程度。贝叶斯定理&#xff1a;用于推断和分类中的后验概率计算。假设检验&#xff1a;评估模型的性能和数据显著性。…

Scala入门基础(17.1)Set集习题

一.选择题 二.实训 图书馆书籍管理系统相关的练习。内容要求&#xff1a; 1.创建一个可变 Set&#xff0c;用于存储图书馆中的书籍信息 &#xff08;假设书籍信息用字符串表示&#xff0c;如“Java编程思想”“Scala实战”等&#xff09; 2.添加两本新的书籍到图书馆集合中&a…

移动端【01】面试系统的MVVM重构实践

基于MVVM的移动端面试系统重构实践&#xff1a;模块化设计与实现 一、项目背景 面试记录表系统在经过一年多的迭代后&#xff0c;代码质量问题日益突出。View和ViewModel代码均超过3000行&#xff0c;组件引用超过1000个&#xff0c;亟需进行架构重构。本文将详细介绍基于MVV…

Springboot 启动端口占用如何解决

Springboot 启动端口占用如何解决 1、报错信息如下 *************************** APPLICATION FAILED TO START ***************************Description:Web server failed to start. Port 9010 was already in use.Action:Identify and stop the process thats listening o…

基于Python+Django+Vue3+MySQL实现的前后端分类的商场车辆管理系统

项目名称&#xff1a;基于PythonDjangoVue3MySQL实现的前后端分离商场车辆管理系统 技术栈 开发工具&#xff1a;PyCharm、Visual Studio Code (VSCode)运行环境&#xff1a;Python 3.10、MySQL 8.0、Node.js 18技术框架&#xff1a;Django 5、Vue 3.4、Ant-Design-Vue 4.12 …

ML 系列: 第 23 节 — 离散概率分布 (多项式分布)

目录 一、说明 二、多项式分布公式 2.1 多项式分布的解释 2.2 示例 2.3 特殊情况&#xff1a;二项分布 2.4 期望值 &#xff08;Mean&#xff09; 2.5 方差 三、总结 3.1 python示例 一、说明 伯努利分布对这样一种情况进行建模&#xff1a;随机变量可以采用两个可能的值&#…

Openstack7--安装消息队列服务RabbitMQ

只需要在控制节点安装 安装RabbitMQ yum -y install rabbitmq-server 启动RabbitMQ并设置开机自启 systemctl start rabbitmq-server;systemctl enable rabbitmq-server 创建 rabbitmq 用户 并设置密码为 000000 rabbitmqctl add_user rabbitmq 000000 如果你不慎创错了…

图像处理实验二(Image Understanding and Basic Processing)

图像理解&#xff08;Image Understanding&#xff09;和基本图像处理&#xff08;Basic Image Processing&#xff09;是计算机视觉领域的重要组成部分。它们涉及从图像中提取有用信息、分析图像内容、并对其进行处理以达到特定目的。图像理解通常包括识别、分类和解释图像中的…

第74期 | GPTSecurity周报

GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区&#xff0c;集成了生成预训练Transformer&#xff08;GPT&#xff09;、人工智能生成内容&#xff08;AIGC&#xff09;以及大语言模型&#xff08;LLM&#xff09;等安全领域应用的知识。在这里&#xff0c;您可以找…