[Leetcode] Graph Valid Tree 圖與樹

luqiuwen 發布于2019-08-14 12:36 / 2072人閱讀

摘要：這樣就將一個集合的節點歸屬到同一個集合號下了。最后如果并查集中只有一個集合，則說明可以構建樹。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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