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

ops/2024/11/14 9:01:31/

此题在卡码网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.ppmy.cn/ops/133521.html

相关文章

30 秒!用通义灵码画 SpaceX 星链发射流程图

不想读前人“骨灰级”代码&#xff0c; 不想当“牛马”程序员&#xff0c; 想像看图片一样快速读复杂代码和架构&#xff1f; 来了&#xff0c;灵码又加新 buff&#xff01;&#xff01; 通义灵码支持代码逻辑可视化&#xff0c; 可以把你的每段代码画成流程图。 你可以把…

无人机丢失:高效找回的科普指南

无人机作为现代科技的结晶&#xff0c;在多个领域发挥着重要作用&#xff0c;但无人机丢失的情况也时有发生。为了帮助您有效找回丢失的无人机&#xff0c;本文将结合科普知识与实用步骤&#xff0c;提供一套全面的解决方案。 一、启动智能功能 使用GPS定位&#xff1a;如果无人…

Eclipse 首选项(Preferences) 深入解析

Eclipse 首选项(Preferences) 深入解析 Eclipse 是一款广受欢迎的集成开发环境&#xff08;IDE&#xff09;&#xff0c;它为各种编程语言提供了强大的开发工具。Eclipse 的首选项&#xff08;Preferences&#xff09;是其核心功能之一&#xff0c;允许用户根据个人喜好和项目…

DevExpress WinForms中文教程:Data Grid - 如何绑定到实体框架数据源?

在本教程中&#xff0c;您将学习如何将DevExpress WinForms的网格控件绑定到实体框架数据源、如何使用数据注释属性来更改网格显示和管理数据的方式&#xff0c;以及如何将单元格值更改发送回数据源。 P.S&#xff1a;DevExpress WinForms拥有180组件和UI库&#xff0c;能为Wi…

深入理解面向对象编程(OOP):从基础到进阶

深入理解面向对象编程&#xff08;OOP&#xff09;&#xff1a;从基础到进阶 一、引言 在编程的广袤领域中&#xff0c;面向对象编程&#xff08;Object - Oriented Programming&#xff0c;OOP&#xff09;宛如一颗璀璨的明珠&#xff0c;闪耀着独特的光芒。它不仅仅是一种编…

系统安全第七次作业题目及答案

一、 1.RBAC0 RBAC1 RBAC2 RBAC3 2.属性 身份标识 3.接入访问控制 资源访问控制 网络端口和节点的访问控制 二、 1.B 2.A 3.ABE 4.BCD 5.ABC 三、 1. 答&#xff1a;基于属性的访问控制&#xff08;ABAC&#xff09;是通过对实体属性添加约束策略的方式实现主、客体之…

12LangChain实战课 - ReAct框架与代理的应用

LangChain实战课 - ReAct框架与代理的应用 在本次LangChain实战课程中&#xff0c;我们深入探讨了ReAct框架以及代理&#xff08;Agent&#xff09;在大语言模型中的应用。以下是本次课程的核心内容和要点&#xff1a; 1. ReAct框架的介绍 ReAct框架是一种指导大语言模型&am…

【动态规划】打家劫舍类问题

一、按摩师 17.16. 按摩师 题目描述&#xff1a; 题目分析&#xff1a; 1、状态表示 每个预约都只会有两种选择&#xff0c;即选或不选。因此我们可以用 dp[i][0] 表示不选择第 i 个预约时&#xff0c;最长的预约时长dp[i][1] 表示选择第 i 个预约时&#xff0c;最长的预…