面试算法118:多余的边

发布时间:2024年01月12日

题目

树可以看成无环的无向图。在一个包含n个节点(节点标号为从1到n)的树中添加一条边连接任意两个节点,这棵树就会变成一个有环的图。给定一个在树中添加了一条边的图,请找出这条多余的边(用这条边连接的两个节点表示)。输入的图用一个二维数组edges表示,数组中的每个元素是一条边的两个节点[u,v](u<v)。如果有多个答案,请输出在数组edges中最后出现的边。
例如,如果输入数组edges为[[1,2],[1,3],[2,4],[3,4],[2,5]],则它对应的无向图如图15.25所示。输出为边[3,4]。
在这里插入图片描述

分析

先在图中添加一条边[1,2],于是将节点1和节点2所在的子图连在一起,形成一个有两个节点的子图,如图(a)所示。接下来添加一条边[1,3]。由于节点1和节点3分别属于两个不同的子图,添加这条边就将两个子图连成一个包含3个节点的子图,如图(b)所示。再在图中添加一条边[2,4]。由于节点2和节点4分别属于两个不同的子图,添加这条边就将两个子图连成一个包含4个节点子图,如图(c)所示。然后在图中添加一条边[3,4]。此时节点3和节点4属于同一个子图,添加边[3,4]导致图中出现了一个环,如图(d)所示。最后添加边[2,5]。节点2和节点5属于不同的子图,这条边将两个子图连在一起形成一个包含5个节点的子图。
在这里插入图片描述

public class Test {
    public static void main(String[] args) {
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {2, 5}};
        int[] result = findRedundantConnection(edges);
        System.out.println(result[0] + " " + result[1]);
    }

    public static int[] findRedundantConnection(int[][] edges) {
        int maxVertex = 0;
        for (int[] edge : edges) {
            maxVertex = Math.max(maxVertex, edge[0]);
            maxVertex = Math.max(maxVertex, edge[1]);
        }

        int[] fathers = new int[maxVertex + 1];
        for (int i = 1; i <= maxVertex; i++) {
            fathers[i] = i;
        }

        for (int[] edge : edges) {
            if (!union(fathers, edge[0], edge[1])) {
                return edge;
            }
        }

        return new int[2];
    }

    private static boolean union(int[] fathers, int i, int j) {
        int fatherOfI = findFather(fathers, i);
        int fatherOfJ = findFather(fathers, j);
        if (fatherOfI != fatherOfJ) {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }

        return false;
    }

    private static int findFather(int[] fathers, int i) {
        if (fathers[i] != i) {
            fathers[i] = findFather(fathers, fathers[i]);
        }

        return fathers[i];
    }

}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135553573
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。