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

相关文章

扫码关注云+社区