当前位置： 首页 > article >正文

LeetCode 0685.冗余连接 II：并查集（和I有何不同分析）——详细题解(附图)

article 2024/11/5 13:48:18

【LetMeFly】685.冗余连接 II：并查集（和I有何不同分析）——详细题解(附图)

力扣题目链接：https://leetcode.cn/problems/redundant-connection-ii/

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

 

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

 

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n

解题方法：并查集

并查集

解题思路

这题和684.冗余连接的区别是：

684的无向图只需要考虑有没有形成自环，而本题有向图还需要考虑“是否形成了入度为2的节点”。

如果形成了“入度为2”的节点，例如下面两种情况，在684.冗余连接中只需要移除“首次形成(无向)环”的边，而在685.冗余连接II中就不能只移除“最后出现的导致形成(无向)环的边”：

1----->2      1------+
↑      ↑      ↑      ↓
3------+      2<-----3<---4

左图中只能移除[1,2]或[3,2]而不能移除[3,1]；右图中只能移除[1,3]而不能移除[3,2]或[2,1]。

有向边不能和无向边一概而论的本质原因是：树中一个节点不能有两个父节点，即入度不能为2。所以，一旦出现了入度为2的节点 n o d e node node，就要在“终点为 n o d e node node的两条边”里面选择一条移除。判断方法如下：

尝试移除一条边，判断剩下的边（不考虑方向）能否构成无向环，如果不构成无向环则说明这条边可以被移除。

判断方法就和684题一模一样了，使用并查集即可完成判断。

树上多一条边就一定存在入度为2的节点吗？不一定，还可能有以下这种情况：

1------+
↑      ↓
2<-----3----->4

图中节点[1,2,3]形成了一个环，但1、2、3、44个节点的入度都为1。

这样就和684题一模一样了其实，在环[1,2,3]里任意移除一条边图都能变成树。

同样使用并查集，返回第一条“形成环”的边即为所求。

解题方法

首先统计是否有入度为2的节点：

  • 若有，则尝试移除指向2的边（若移除后图中无环则这条边可以被移除）
  • 否则，移除第一条导致“环出现”的边

常见问题回答Q&A

Q1： 若有入度为2的节点，在判断“移除一条边后图是否为树”时，能否通过“统计每个点是否孤立(入度出度都为0)”来判断？

例如下图中终点为3的边有[1,3]和[4,3]两条，移除[4,3]的话会导致点4成为孤立点，因此只能移除[1,3]。

1------+
↑      ↓
2<-----3<---4

A1： 不能这么判断。例如下图只能移除[2,4]不能移除[5,2]，但其实移除其中的任意一条都不会产生“孤立点”。

+---+
↓   ↑
4-->2
    ↑
1-->5-->3

建议修改为“通过判断图是否联通”的方式判断某条边是否可以移除。

时空复杂度

  • 时间复杂度最坏 O ( n log ⁡ n ) O(n\log n) O(nlogn)，平均为 O ( n α ( n ) ) O(n\alpha(n)) O(nα(n))（接近 O ( n ) O(n) O(n)）
  • 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++
class Solution {
private:
    vector<int> fa;

    bool couldRemoveThisEdge(vector<vector<int>>& edges, int index) {
        initFa(edges.size());
        for (int i = 0; i < edges.size(); i++) {
            if (i == index) {
                continue;
            }
            if (find(edges[i][0]) == find(edges[i][1])) {
                return false;
            }
            union_(edges[i][0], edges[i][1]);
        }
        return true;
    }

    vector<int> solution_indegree(vector<vector<int>>& edges, int node) {
        for (int i = edges.size() - 1; i >= 0; i--) {
            if (edges[i][1] == node && couldRemoveThisEdge(edges, i)) {
                return edges[i];
            }
        }
        return {};  // FAKE RETURN
    }

    int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    void union_(int x, int y) {
        fa[find(x)] = find(y);
    }

    void initFa(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
    }

    vector<int> solution_unionFind(vector<vector<int>>& edges) {
        initFa(edges.size());
        for (vector<int>& edge : edges) {
            if (find(edge[0]) == find(edge[1])) {
                return edge;
            } else {
                union_(edge[0], edge[1]);
            }
        }
        return {};  // FAKE RETURN
    }
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        vector<bool> inDegree(edges.size() + 1);
        for (vector<int>& edge : edges) {
            if (inDegree[edge[1]]) {  // 找到了入度为2的点
                return solution_indegree(edges, edge[1]);
            } else {
                inDegree[edge[1]] = true;
            }
        }
        return solution_unionFind(edges);
    }
};
Python
from typing import List

class Solution:
    def initFa(self) -> None:
        for i in range(1, len(self.edges) + 1):
            self.fa[i] = i
    
    def find(self, x: int) -> int:
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def union(self, x: int, y: int) -> None:
        self.fa[self.find(x)] = self.find(y)
    
    def couldRemoveThisEdge(self, index: int) -> bool:
        self.initFa()
        for i in range(len(self.edges)):
            if i == index:
                continue
            if self.find(self.edges[i][0]) == self.find(self.edges[i][1]):
                return False
            else:
                self.union(self.edges[i][0], self.edges[i][1])
        return True

    def solution_indegree(self, node: int) -> List[int]:
        for i in range(len(self.edges) - 1, -1, -1):
            if self.edges[i][1] == node and self.couldRemoveThisEdge(i):
                return self.edges[i]
        return []  # FAKE RETURN

    def solution_unionFind(self) -> List[int]:
        self.initFa()
        for x, y in self.edges:
            if self.find(x) == self.find(y):
                return [x, y]
            else:
                self.union(x, y)
        return []  # FAKE RETURN
    
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        self.fa = [0] * (len(edges) + 1)
        self.edges = edges
        hasIndegree = [False] * (len(edges) + 1)
        for x, y in edges:
            if hasIndegree[y]:
                return self.solution_indegree(y)
            else:
                hasIndegree[y] = True
        return self.solution_unionFind()
Java
class UnionFind {
    private int[] fa;

    public UnionFind(int n) {
        fa = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
    }

    private int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    public boolean isUnion(int x, int y) {
        return find(x) == find(y);
    }

    public void union(int x, int y) {
        fa[find(x)] = find(y);
    }
}

class Solution {
    private boolean canRemoveThisEdge(int[][] edges, int index) {
        UnionFind unionFind = new UnionFind(edges.length);
        for (int i = 0; i < edges.length; i++) {
            if (i == index) {
                continue;
            }
            if (unionFind.isUnion(edges[i][0], edges[i][1])) {
                return false;
            } else {
                unionFind.union(edges[i][0], edges[i][1]);
            }
        }
        return true;
    }

    private int[] solution_indegree(int[][] edges, int node) {
        for (int i = edges.length - 1; i >= 0; i--) {
            if (edges[i][1] == node && canRemoveThisEdge(edges, i)) {
                return edges[i];
            }
        }
        return new int[0];  // FAKE RETURN
    }

    private int[] solution_unionFind(int[][] edges) {
        UnionFind unionFind = new UnionFind(edges.length);
        for (int[] edge : edges) {
            if (unionFind.isUnion(edge[0], edge[1])) {
                return edge;
            } else {
                unionFind.union(edge[0], edge[1]);
            }
        }
        return new int[0];  // FAKE RETURN
    }
    
    public int[] findRedundantDirectedConnection(int[][] edges) {
        boolean[] hasIndegree = new boolean[edges.length + 1];
        for (int[] edge : edges) {
            if (hasIndegree[edge[1]]) {
                return solution_indegree(edges, edge[1]);
            } else {
                hasIndegree[edge[1]] = true;
            }
        }
        return solution_unionFind(edges);
    }
}
Go
package main

type UnionFind struct {
    fa []int
}

func New(n int) UnionFind {
    fa := make([]int, n + 1)
    for th, _ := range fa {
        fa[th] = th
    }
    return UnionFind{fa}
}

func (unionFind UnionFind) _find(x int) int {
    if unionFind.fa[x] != x {
        unionFind.fa[x] = unionFind._find(unionFind.fa[x])
    }
    return unionFind.fa[x]
}

func (unionFind UnionFind) isUnion(x, y int) bool {
    return unionFind._find(x) == unionFind._find(y)
}

func (unionFind UnionFind) union(x, y int) {
    unionFind.fa[unionFind._find(x)] = unionFind._find(y)
}

func canRemoveThisEdge(edges [][]int, index int) bool {
    unionFind := New(len(edges))
    for i := 0; i < len(edges); i++ {
        if i == index {
            continue
        }
        if unionFind.isUnion(edges[i][0], edges[i][1]) {
            return false
        } else {
            unionFind.union(edges[i][0], edges[i][1])
        }
    }
    return true
}

func solution_indegree(edges [][]int, node int) []int {
    for i := len(edges) - 1; i >= 0; i-- {
        if edges[i][1] == node && canRemoveThisEdge(edges, i) {
            return edges[i]
        }
    }
    return make([]int, 0)  // FAKE RETURN
}

func solution_unionFind(edges [][]int) []int {
    unionFind := New(len(edges))
    for _, edge := range edges {
        if unionFind.isUnion(edge[0], edge[1]) {
            return edge
        } else {
            unionFind.union(edge[0], edge[1])
        }
    }
    return make([]int, 0)  // FAKE RETURN
}

func findRedundantDirectedConnection(edges [][]int) []int {
    hasIndegree := make([]bool, len(edges) + 1)
    for _, edge := range edges {
        if hasIndegree[edge[1]] {
            return solution_indegree(edges, edge[1])
        } else {
            hasIndegree[edge[1]] = true
        }
    }
    return solution_unionFind(edges)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143470538


http://www.kler.cn/a/378592.html

相关文章：

  • LeetCode46. 全排列（2024秋季每日一题 57）
  • 华为od技术一面
  • 服务器作业（2）
  • 【jvm】如何设置新生代和老年代的比例
  • 2、liunx网络基础
  • 软件测试基础六 （Linux）
  • ReactNative Fabric渲染器和组件(5)
  • 【NLP自然语言处理】深入解析Encoder与Decoder模块：结构、作用与深度学习应用
  • 简单题:Base32 编码和解码问题| 豆包MarsCode AI刷题
  • 【多线程奇妙屋】收藏多年的线程安全问题大全笔记(下篇) { 死锁问题 }，笔记一生一起走，那些日子不再有
  • STM32 第22章 常用存储器介绍
  • JavaScript 判断数据类型有哪些方法？
  • 1、DevEco Studio 鸿蒙仓颉应用创建
  • Gradient descent algorithm
  • express搭建ts（TypeScript）运行环境
  • ChatGPT、Python和OpenCV支持下的空天地遥感数据识别与计算
  • 关联容器笔记
  • 【天线＆空中农业】草莓果实检测系统源码＆数据集全套：改进yolo11-HSFPN
  • 【华为HCIP实战课程31（完整版）】中间到中间系统协议IS-IS路由汇总详解，网络工程师
  • 使用ssh-key免密登录服务器或免密连接git代码仓库网站
  • ASAN ThreadSanitizer定位多线程（资源管理）
  • LabVIEW过程控制实验平台
  • Flutter InkWell组件去掉灰色遮罩
  • C#医学检验信息系统LIS源码，医院检验科信息管理系统源码
  • 编程八种语言谁是最受市场青睐的？
  • 【已解决】cra 配置路径别名 @ 后，出现 ts 报错：找不到模块“@/App”或其相应的类型声明。ts(2307)