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

这篇具有很好参考价值的文章主要介绍了图论|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的边的一条 判断删除后是不是树即可
再使用并查集判断是否有环(是否有冲突 此时的冲突一定是构成环)
如何使用并查集判断删除后是不是树
因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根,那么这条边添加上之后 这个图一定不是树了
如何使用并查集判断判断是否有环(有环时 附加的边指向根节点)
附加的边指向根节点,而且是在环路中的最后一条被访问到的边文章来源地址https://www.toymoban.com/news/detail-763639.html


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的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 图论

    目录 797.所有可能得路径  200.岛屿数量 695.岛屿的最大面积 1020.飞地的数量  130.被围绕的区域  417.太平洋大西洋水流问题  827.最大人工岛 127.单词接龙  841.钥匙和房间 463.岛屿的周长  797. 所有可能的路径 中等 给你一个有  n  个节点的  有向无环图(DAG) ,请你找出所有从

    2024年04月10日
    浏览(42)
  • 代码随想录(番外)图论1

    1. 深度优先搜索理论基础 2. 所有可能的路径 3. 广度优先搜索理论基础.md https://programmercarl.com/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 1. 深度优先搜索理论基础 总结 同理回溯算法,换汤不换药 二叉树递归讲解 (opens new window)中,给出了递归三部曲。 回溯算

    2024年04月28日
    浏览(39)
  • 代码随想录(番外)图论4

    417. 太平洋大西洋水流问题 那么我们可以 反过来想,从太平洋边上的节点 逆流而上,将遍历过的节点都标记上。 从大西洋的边上节点 逆流而长,将遍历过的节点也标记上。 然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。 也就是说通过从两边的大洋开

    2024年04月29日
    浏览(58)
  • 代码随想录:55. 跳跃游戏;45. 跳跃游戏 II

    给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 示例 2: 其实跳几步无所谓,关键在于可跳的覆盖范围! 不一定非要明确一次究竟跳几步,每次取最

    2023年04月11日
    浏览(47)
  • 代码随想录 Leetcode142. 环形链表 II

            双指针解决百分之99的链表题

    2024年01月19日
    浏览(43)
  • 代码随想录第39天 | 62.不同路径 、 63. 不同路径 II

    一、前言 参考文献:代码随想录 今天主要的题目是动态规划的路径问题,动态规划五要点; 1、确定dp数组,dp[i]代表什么i代表什么; 2、递推公式; 3、初始化dp数组; 4、遍历顺序; 5、打印dp数组; 二、不同路径 1、思路: 我感觉动态规划,我听的很认真,然后这个题目,

    2024年04月13日
    浏览(41)
  • 代码随想录图论 第五天| 841.钥匙和房间 463. 岛屿的周长

    代码随想录图论 第五天| 841.钥匙和房间 一、 841.钥匙和房间 题目链接:https://leetcode.cn/problems/keys-and-rooms/ 思路:钥匙就是索引,遍历过就标记,每拿到一个房间的钥匙,直接for循环递归遍历,深度优先直接拿下。 二、463. 岛屿的周长 题目链接:https://leetcode.cn/problems/island-

    2024年02月06日
    浏览(46)
  • 代码随想录图论 第一天 | 797.所有可能的路径 200. 岛屿数量

    代码随想录图论 第一天 | 797.所有可能的路径 200. 岛屿数量 一、797.所有可能的路径 题目链接:https://leetcode.cn/problems/all-paths-from-source-to-target/ 思路:求从0到n-1的所有路径,终止条件是当前节点为n-1。本题图的结构是group[][],group[x]表示x节点所能到达的所有节点的集合,深度

    2024年02月08日
    浏览(54)
  • 代码随想录23| 93.复原IP地址, 78.子集, 90.子集II

    题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址

    2024年02月11日
    浏览(87)
  • 代码随想录Day42-图论:力扣第417m、841m、463e题

    题目链接 代码随想录文章讲解链接 方法一: 用时:1h0m58s 思路 直接找哪些点既可以到达太平洋又可以到达大西洋比较麻烦,换个角度,找到太平洋可以逆流而上到达的点,再找到大西洋可以逆流而上到达的点,两者的交集就是所需要的答案。 用两个二维数组分别记录太平洋

    2024年02月05日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包