代码随想录Day56 108. 冗余连接，109. 冗余连接II。

1.冗余连接

卡码网题目链接（ACM模式）(opens new window)

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3

输出示例

1 3

提示信息

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

思路

这道题目也是并查集基础题目。

这里我依然降调一下，并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。

如果还不了解并查集，可以看这里：并查集理论基础

我们再来看一下这道题目。

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如图所示，节点A 和节点 B 不在同一个集合，那么就可以将两个 节点连在一起。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

如图所示：

已经判断 节点A 和 节点B 在在同一个集合（同一个根），如果将 节点A 和 节点B 连在一起就一定会出现环。

这个思路清晰之后，代码就很好写了。

拓展

题目要求 “请删除标准输入中最后出现的那条边” ，不少录友疑惑，这代码分明是遇到在同一个根的两个节点立刻就返回了，怎么就求出 最后出现的那条边 了呢。

有这种疑惑的录友是 认为发现一条冗余边后，后面还可能会有一条冗余边。

其实并不会。

题目是在 树的基础上 添加一条边，所以冗余边仅仅是一条。

到这一条可能靠前出现，可能靠后出现。

例如，题目输入示例：

输入示例

3
1 2
2 3
1 3

图：

输出示例

1 3

当我们从前向后遍历，优先让前面的边连上，最后判断冗余边就是 1 3。

如果我们从后向前便利，优先让后面的边连上，最后判断的冗余边就是 1 2。

题目要求“请删除标准输入中最后出现的那条边”，所以 1 3 这条边才是我们要求的。

public class Redundant_Connection {
    private int[] parent;//parent 数组存储每个节点的父节点。
    private int[] rank;//rank 数组存储每个集合的排名，用于优化合并操作。
    public Redundant_Connection(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    private int find(int x) {//find 方法用于查找节点的根节点，并进行路径压缩。
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {//union 方法用于合并两个节点的集合。
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            rank[rootX] += rank[rootY];
        } else {
            parent[rootX] = rootY;
            rank[rootY] += rank[rootX];
        }
        return true;
    }

    public static int[] findRedundantConnection(int[][] edges) {//接受一个边的数组，使用并查集来检测冗余连接。遍历所有边，尝试合并每条边连接的两个节点。如果两个节点已经在同一个集合中，则当前边是冗余连接。
        int n = edges.length + 1;
        Redundant_Connection rc = new Redundant_Connection(n);
        for (int[] edge : edges) {
            if (!rc.union(edge[0], edge[1])) {
                return edge;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {//读取节点数和边数。读取所有边的信息。调用 findRedundantConnection 方法找到冗余连接，并输出结果。
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            edges[i][0] = scanner.nextInt();
            edges[i][1] = scanner.nextInt();
        }
        int[] redundantEdge = findRedundantConnection(edges);
        System.out.println("Redundant connection: " + Arrays.toString(redundantEdge));
        scanner.close();
    }
}

• 时间复杂度：O(mα(n))，其中m是边数，n是节点数，α是阿克曼函数的反函数，对于所有实际输入都是一个非常小的常数
• 空间复杂度：O(n)，用于存储并查集的数据结构

2.冗余连接II

卡码网题目链接（ACM模式）(opens new window)

题目描述

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例

3
1 2
1 3
2 3

1
2
3
4

输出示例

2 3

提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3

数据范围：

1 <= N <= 1000.

思路

本题与 108.冗余连接 类似，但本题是一个有向图，有向图相对要复杂一些。

本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树。

还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边！

我们来想一下 有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。

如图：

找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删顺序靠后便可。

但 入度为2 还有一种情况，情况二，只能删特定的一条边，如图：

节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。

综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环）。

如图：

对于情况三，删掉构成环的边就可以了。

写代码

把每条边记录下来，并统计节点入度

前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案。

同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为树，就删最后那一条。

再来看情况三，明确没有入度为2的情况，那么一定有向环，找到构成环的边就是要删除的边。

可以定义一个函数。

大家应该知道了，我们要解决本题要实现两个最为关键的函数：

• isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树
• getRemoveEdge() 确定图中一定有了有向环，那么要找到需要删除的那条边

此时就用到并查集了。

如果还不了解并查集，可以看这里：并查集理论基础(opens new window)

isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树： 将所有边的两端节点分别加入并查集，遇到要 要删除的边则跳过，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。

如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明 删除该条边 还是一个有向树

getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边： 将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。

public class Redundant_ConnectionII {
    static int n;// 存储图中节点的数量。
    static int[] father = new int[1001];//用于存储每个节点的父节点信息，初始化为自身，表示每个节点最初都是独立的集合。
    public static void init() {//初始化并查集，将每个节点的父节点设置为自身。
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
        }
    }
    public static int find(int u) {//并查集的查找操作，用于找到节点u的根节点，并进行路径压缩以优化后续查找。
        if (u == father[u]) return u;
        return father[u] = find(father[u]);
    }
    public static void join(int u, int v) {//并查集的合并操作，用于合并节点u和v所在的集合。
        u = find(u);
        v = find(v);
        if (u != v) {
            father[v] = u;
        }
    }
    public static boolean same(int u, int v) {//检查两个节点u和v是否在同一个集合中。
        return find(u) == find(v);
    }
    public static void getRemoveEdge(List<int[]> edges) {//遍历所有边，使用并查集检查是否存在冗余连接。如果发现两个节点已经在同一个集合中，则输出这条边作为冗余连接并返回。
        init();
        for (int i = 0; i < n; i++) {
            if (same(edges.get(i)[0], edges.get(i)[1])) {
                System.out.println(edges.get(i)[0] + " " + edges.get(i)[1]);
                return;
            } else {
                join(edges.get(i)[0], edges.get(i)[1]);
            }
        }
    }
    public static boolean isTreeAfterRemoveEdge(List<int[]> edges, int deleteEdge) {//检查在移除特定边deleteEdge后，图是否仍然是一棵树（连通且无环）。如果在移除边后图仍然连通，则返回true。
        init();
        for (int i = 0; i < n; i++) {
            if (i == deleteEdge) continue;
            if (same(edges.get(i)[0], edges.get(i)[1])) {
                return false;
            }
            join(edges.get(i)[0], edges.get(i)[1]);
        }
        return true;
    }

    public static void main(String[] args) {//使用Scanner类从标准输入读取数据。读取节点数n和边数，以及所有边的信息。初始化一个inDegree数组来存储每个节点的入度。遍历所有边，更新入度数组，并收集所有入度为2的边的索引到vec列表中。如果vec列表不为空，说明找到了至少一条冗余连接。调用isTreeAfterRemoveEdge方法检查移除这些边后图是否仍然是一棵树，如果是，则输出这条边；否则，输出vec列表中另一条边。如果vec列表为空，说明没有找到入度为2的边，调用getRemoveEdge方法来寻找冗余连接。
        Scanner sc = new Scanner(System.in);
        List<int[]> edges = new ArrayList<>();

        n = sc.nextInt();
        int[] inDegree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            inDegree[t]++;
            edges.add(new int[]{s, t});
        }

        List<Integer> vec = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges.get(i)[1]] == 2) {
                vec.add(i);
            }
        }
        if (vec.size() > 0) {
            if (isTreeAfterRemoveEdge(edges, vec.get(0))) {
                System.out.println(edges.get(vec.get(0))[0] + " " + edges.get(vec.get(0))[1]);
            } else {
                System.out.println(edges.get(vec.get(1))[0] + " " + edges.get(vec.get(1))[1]);
            }
            return;
        }
        getRemoveEdge(edges);
    }
}

• 时间复杂度：O(N + Mα(N))，其中N是节点数，M是边数，α是阿克曼函数的反函数，对于所有实际输入都是一个非常小的常数。
• 空间复杂度：O(N)，用于存储并查集的数据结构。