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 条评论
登录 后参与评论

相关文章

来自专栏算法修养

ZOJ 3715 Kindergarten Election

At the beginning of the semester in kindergarten, the n little kids (indexed fro...

2724
来自专栏开发与安全

《dive into python3》 笔记摘录

0、In Python 2, the / operator usually meant integer division, but you could make...

2220
来自专栏杨熹的专栏

【LEETCODE】模拟面试-294.Flip Game II

图:新生大学 You are playing the following Flip Game with your friend: Given a string...

3468
来自专栏C语言及其他语言

[蓝桥杯]Hello, world!

题目描述 This is the first problem for test. Since all we know the ASCII code, your ...

3318
来自专栏杨建荣的学习笔记

MySQL级联复制中的数据同步(第二篇)(r11笔记第21天)

今天还是说说级联复制的问题情况,因为架构做了调整,我们要删除其中的一个中继节点(新加坡节点),而直接使用北京节点去连接北美的节点。 更多的信息可以参考。 MyS...

34412
来自专栏算法修养

PAT 甲级 1023 Have Fun with Numbers

1023. Have Fun with Numbers (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 160...

2507
来自专栏杨熹的专栏

【LEETCODE】模拟面试-120- Triangle

题目: https://leetcode.com/problems/triangle/ Given a triangle, find the minimum ...

3064
来自专栏Petrichor的专栏

leetcode: 75. Sort Colors

1203
来自专栏码匠的流水账

聊聊pg jdbc statement的maxRows参数

postgresql-9.4.1212.jre7-sources.jar!/org/postgresql/core/v3/QueryExecutorImpl.j...

582
来自专栏机器学习入门

LWC 58:724. Find Pivot Index

LWC 58:724. Find Pivot Index 传送门:724. Find Pivot Index Problem: Given an array ...

1808

扫码关注云+社区