[leetcode]图/树算法之并查集Redundant Connection（环/回路的判定）

缺乏、安全感 2021-09-28 14:30 342阅读 0赞

### 图/树算法之并查集 ###

*  题目
 *  解析
 *  答案
 *  知识点

# 题目 #

[leetcode入口][leetcode]

# 解析 #

这一道题运用了并查集，  
并查集知识，参考[博客入口][Link 1]

在并查集的数组里，如果有相同的祖先，说明在同一颗树中，  
因此如果一条边的两个点，有共同的祖先，说明他们在一颗树里。  
此时再在两个点间连一条线，那么就会使得树中出现环。

# 答案 #

class Solution{ 
    public:
        vector<int> findRedundantConnection(vector<vector<int>>& edges){ 
            vector<int> root(2001,-1);
            
            for(vector<int> edge : edges){ 
                //找到两个顶点的祖先
                int x=find(root,edge[0]); 
                int y=find(root,edge[1]);
                
                if(x==y) return edge;
                
                //设置x的祖先为y，也可以理解为合并祖先为x和祖先为y的两颗树（图）
                root[y]=x;
            }
            return { };
        }
            
            
        
        int find(vector<int> & root,int i){ 
                while(root[i]!=-1){ 
                    i=root[i];
                }
                return i;
        }
            
    };

# 知识点 #

并查集，图判环，树

[leetcode]: https://leetcode.com/problems/redundant-connection/
[Link 1]: https://blog.csdn.net/qq_41593380/article/details/81146850

发表评论取消回复

表情：

评论列表（有 0 条评论，342人围观）

还没有评论，来说两句吧...

相关阅读

相关篮球杯【并查集】发现环

[发现环 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题意: ![aa1bcadefde095cbab2818e729c3fa3d.png]

谁践踏了优雅/ 2024年03月25日 10:14/ 0 赞/ 55 阅读

相关并查集算法

文章目录 1. 原理介绍 2. 并查集的应用 3. find()函数的定义与实现 4. 并查集的join函数

以你之姓@/ 2024年03月22日 15:46/ 0 赞/ 73 阅读

相关【HDU】1878 欧拉回路题解（并查集 + 无向图欧拉回路）

> 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1878][http_acm.hdu.edu.cn_showpro

- 日理万妓/ 2023年07月14日 10:54/ 0 赞/ 23 阅读

相关算法刻意练习之字典树/并查集

1 字典树 1.1 特点又叫Trie树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构 1.2 对比树、二叉搜索树（1）树 !

ゝ一纸荒年。/ 2022年12月21日 06:09/ 0 赞/ 212 阅读

相关树的应用——并查集

首先，什么是并查集？并查集是一种简单的集合表示。我们可以简单的思考一下这个名字，“集”应该就是集合的意思，而“并”和“查”，估计是两种动作或者形容。这个我们后面慢慢就知

谁借莪１个温暖的怀抱￠/ 2022年11月09日 12:40/ 0 赞/ 169 阅读

相关 HDU 1272(并查集求无向图环)

include <iostream> include <cstring> using namespace std; int s

桃扇骨/ 2022年09月20日 12:42/ 0 赞/ 159 阅读

相关 leetcode 685. Redundant Connection II 有向图的环的查询 + 并查集Union Find

In this problem, a rooted tree is a directed graph such that, there is exactly one node

素颜马尾好姑娘i/ 2022年06月03日 09:24/ 0 赞/ 107 阅读

相关 POJ 2513 Colored Sticks(字典树 + 并查集 + 欧拉回路)

<table> <tbody> <tr> <td> <p><strong>Colored Sticks</strong></p> <div>

浅浅的花香味﹌/ 2021年11月02日 06:32/ 0 赞/ 245 阅读

相关算法：并查集

算法：并查集快速掌握理解算法　　在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合

ゝ一纸荒年。/ 2021年09月30日 11:30/ 0 赞/ 412 阅读

相关 [leetcode]图/树算法之并查集Redundant Connection（环/回路的判定）

图/树算法之并查集题目解析答案知识点题目 [leetcode入口][leetcode] 解析这一道题运用了并查集，

缺乏、安全感/ 2021年09月28日 14:30/ 0 赞/ 343 阅读