LWC 51:684. Redundant Connection

LWC 51:684. Redundant Connection

传送门:684. Redundant Connection

Problem:

We are given a “tree” in the form of a 2D-array, with distinct values for each node. In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree. We can remove exactly one redundant pair in this “tree” to make the result a tree. You need to find and output such a pair. If there are multiple answers for this question, output the one appearing last in the 2D-array. There is always at least one answer.

Example 1:

Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: Original tree will be like this: 1 / \ 2 - 3

Example 2:

Input: [[1,2], [1,3], [3,1]] Output: [3,1] Explanation: Original tree will be like this: 1 / \\ 2 3

Note:

The size of the input 2D-array will be between 1 and 1000.

Every integer represented in the 2D-array will be between 1 and 2000.

思路: 检测是否有冗余的边,意味着一条新的边加入之后,原先的连通性没有发生变化,用并查集即可。判断加入新边时,判断这两个结点在原先的结构中是否被连通,如果连通只能说明此边是冗余的,题目保证只有一条这样的边,所以遇到就能输出。

代码如下:

    class Union{
        int[] id;
        int[] sz;

        Union(int n){
            id = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; ++i) {
                id[i] = i;
            }
            Arrays.fill(sz, 1);
        }

        int find(int i) {
            while (i != id[i]) {
                i = id[i];
            }
            return i;
        }

        boolean same(int i, int j) {
            return find(i) == find(j);
        }

        void union(int i, int j) {
            int p = find(i);
            int q = find(j);
            if (p == q) return;

            if (sz[p] > sz[q]) {
                id[q] = p;
                sz[p] += sz[q];
            }
            else {
                id[p] = q;
                sz[q] += sz[p];
            }
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        Union union = new Union(2000 + 16);
        for (int i = 0; i < n; ++i) {
            if (union.same(edges[i][0], edges[i][1])) return new int[] {edges[i][0], edges[i][1]};
            else {
                union.union(edges[i][0], edges[i][1]);
            }
        }
        return new int[] {-1,-1};
    }      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

2943
来自专栏大数据架构

UML(一) 类图详解

2176
来自专栏python学习指南

python生成式

本篇将介绍Python的列表生成式,更多内容请参考:Python列表生成式 列表生成式即List Comprehensions,是Python内置的非常简...

2038
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数值的整数次方(九度OJ1514)

题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

2037
来自专栏书山有路勤为径

生成括号

已知n组括号,开发一个程序,生成这n组括号所有的合法的组合可能例如:n = 3 结果为:["((())) "," (()())","()(()) "," ()...

671
来自专栏yl 成长笔记

UML 类图基础

定义:两个类之间的强依赖关系, 可以为单向,亦可为双向。常见表现形式 为 A 类中有 B 类型的成员变量。

964
来自专栏机器学习原理

python函数基础字符串操作numpy 和list互相转换

list 转 numpy np.array(a) ndarray 转 list a.tolist() 写入文件必须是字符

1101
来自专栏ThoughtWorks

TW洞见 | 崔鹏飞:Scala中Stream的应用场景及其实现原理

假设一个场景 需要在50个随机数中找到前两个可以被3整除的数字。 听起来很简单,我们可以这样来写: ? 一个产生50个随机数的函数; 一个检查某数字是否能被3...

3284
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

3264
来自专栏mathor

LeetCode75.颜色分类

 这道题两种做法,一种是用计数排序,因为告诉了你只有3种数字,所以直接创建一个长度为3的数组arr,然后遍历一遍原数组,每出现一次某个数,arr对应位置的值...

602

扫码关注云+社区