[Leetcode] Graph Valid Tree 图与树

luqiuwen 发布于2019-08-14 12:36 / 2028人阅读

摘要：这样就将一个集合的节点归属到同一个集合号下了。最后如果并查集中只有一个集合，则说明可以构建树。

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Hint:
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? Show More Hint  Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

并查集 复杂度

时间 O(N^M) 空间 O(1)

思路

判断输入的边是否能构成一个树，我们需要确定两件事：

这些边是否构成环路，如果有环则不能构成树

这些边是否能将所有节点连通，如果有不能连通的节点则不能构成树

因为不需要知道具体的树长什么样子，只要知道连通的关系，所以并查集相比深度优先搜索是更好的方法。我们定义一个并查集的数据结构，并提供标准的四个接口：

union 将两个节点放入一个集合中

find 找到该节点所属的集合编号

areConnected 判断两个节点是否是一个集合

count 返回该并查集中有多少个独立的集合

具体并查集的原理，参见这篇文章。简单来讲，就是先构建一个数组，节点0到节点n-1，刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后，每次union操作时，我们把整个并查集中，所有和第一个节点所属集合号相同的节点的集合号，都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入，把所有边加入我们的并查集中，加的同时判断是否有环路。最后如果并查集中只有一个集合，则说明可以构建树。

注意

因为要判断是否会产生环路，union方法要返回一个boolean，如果两个节点本来就在一个集合中，就返回假，说明有环路

代码

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < edges.length; i++){
            // 如果两个节点已经在同一集合中，说明新的边将产生环路
            if(!uf.union(edges[i][0], edges[i][1])){
                return false;
            }
        }
        return uf.count() == 1;
    }
    
    public class UnionFind {
        
        int[] ids;
        int cnt;
        
        public UnionFind(int size){
            this.ids = new int[size];
            //初始化并查集，每个节点对应自己的集合号
            for(int i = 0; i < this.ids.length; i++){
                this.ids[i] = i;
            }
            this.cnt = size;
        }
        public boolean union(int m, int n){
            int src = find(m);
            int dst = find(n);
            //如果两个节点不在同一集合中，将两个集合合并为一个
            if(src != dst){
                for(int i = 0; i < ids.length; i++){
                    if(ids[i] == src){
                        ids[i] = dst;
                    }
                }
                // 合并完集合后，集合数减一
                cnt--;
                return true;
            } else {
                return false;
            }
        }
        public int find(int m){
            return ids[m];
        }
        public boolean areConnected(int m, int n){
            return find(m) == find(n);
        }
        public int count(){
            return cnt;
        }
    }
}

GPU云服务器云服务器 graph LeetCode graph编程语言 Valid

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64587.html

[LeetCode] Graph Valid Tree [Union Find]

Problem Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Example Given n = 5 and...

104828720 2019-08-14 15:10 评论0 收藏0
[Leetcode] Graph Valid Tree 判断一个图是否为树

摘要：只有一个连通分量还没有环，就是树，无根树。无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑，很像集合，所以非常适合用并查集来解决。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

xbynet 2019-08-14 14:04 评论0 收藏0
261. Graph Valid Tree

摘要：题目链接检查图的连通性及是否有环，可以，，从一个点出发看能不能遍历所有的点，同时来检查是否有环。还可以用检查是否有环，最后看的数量是否等于来判断是不是。 261. Graph Valid Tree 题目链接：https://leetcode.com/problems... 检查图的连通性及是否有环，可以dfs，bfs，从一个点出发看能不能遍历所有的点，同时visited来检查是否有环。...

Jinkey 2019-08-16 10:29 评论0 收藏0
leetcode310. Minimum Height Trees

摘要：现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。然后利用邻接表的相关属性来判断当前节点是否是叶节点。度数为一的顶点就是叶节点。这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。题目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

xiaoxiaozi 2019-08-16 13:46 评论0 收藏0
力扣(LeetCode)662

摘要：每一层的宽度被定义为两个端点该层最左和最右的非空节点，两端点间的节点也计入长度之间的长度。示例输入输出解释最大值出现在树的第层，宽度为。因为，这样做的话时间复杂度是指数级别与树的深度成指数关系。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（fu...

MartinDai 2019-08-16 14:29 评论0 收藏0