亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode] Graph Valid Tree 圖與樹(shù)

luqiuwen / 2117人閱讀

摘要：這樣就將一個(gè)集合的節(jié)點(diǎn)歸屬到同一個(gè)集合號(hào)下了。最后如果并查集中只有一個(gè)集合，則說(shuō)明可以構(gòu)建樹(shù)。

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.
并查集 復(fù)雜度

時(shí)間 O(N^M) 空間 O(1)

思路

判斷輸入的邊是否能構(gòu)成一個(gè)樹(shù)，我們需要確定兩件事：

這些邊是否構(gòu)成環(huán)路，如果有環(huán)則不能構(gòu)成樹(shù)

這些邊是否能將所有節(jié)點(diǎn)連通，如果有不能連通的節(jié)點(diǎn)則不能構(gòu)成樹(shù)

因?yàn)椴恍枰谰唧w的樹(shù)長(zhǎng)什么樣子，只要知道連通的關(guān)系，所以并查集相比深度優(yōu)先搜索是更好的方法。我們定義一個(gè)并查集的數(shù)據(jù)結(jié)構(gòu)，并提供標(biāo)準(zhǔn)的四個(gè)接口：

union 將兩個(gè)節(jié)點(diǎn)放入一個(gè)集合中

find 找到該節(jié)點(diǎn)所屬的集合編號(hào)

areConnected 判斷兩個(gè)節(jié)點(diǎn)是否是一個(gè)集合

count 返回該并查集中有多少個(gè)獨(dú)立的集合

具體并查集的原理，參見(jiàn)這篇文章。簡(jiǎn)單來(lái)講，就是先構(gòu)建一個(gè)數(shù)組，節(jié)點(diǎn)0到節(jié)點(diǎn)n-1，剛開(kāi)始都各自獨(dú)立的屬于自己的集合。這時(shí)集合的編號(hào)是節(jié)點(diǎn)號(hào)。然后，每次union操作時(shí)，我們把整個(gè)并查集中，所有和第一個(gè)節(jié)點(diǎn)所屬集合號(hào)相同的節(jié)點(diǎn)的集合號(hào)，都改成第二個(gè)節(jié)點(diǎn)的集合號(hào)。這樣就將一個(gè)集合的節(jié)點(diǎn)歸屬到同一個(gè)集合號(hào)下了。我們遍歷一遍輸入，把所有邊加入我們的并查集中，加的同時(shí)判斷是否有環(huán)路。最后如果并查集中只有一個(gè)集合，則說(shuō)明可以構(gòu)建樹(shù)。

注意

因?yàn)橐袛嗍欠駮?huì)產(chǎn)生環(huán)路，union方法要返回一個(gè)boolean，如果兩個(gè)節(jié)點(diǎn)本來(lái)就在一個(gè)集合中，就返回假，說(shuō)明有環(huán)路

代碼 
public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < edges.length; i++){
            // 如果兩個(gè)節(jié)點(diǎn)已經(jīng)在同一集合中，說(shuō)明新的邊將產(chǎn)生環(huán)路
            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];
            //初始化并查集，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)自己的集合號(hào)
            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);
            //如果兩個(gè)節(jié)點(diǎn)不在同一集合中，將兩個(gè)集合合并為一個(gè)
            if(src != dst){
                for(int i = 0; i < ids.length; i++){
                    if(ids[i] == src){
                        ids[i] = dst;
                    }
                }
                // 合并完集合后，集合數(shù)減一
                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;
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64587.html

相關(guān)文章

  • [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 評(píng)論0 收藏0

  • [Leetcode] Graph Valid Tree 判斷一個(gè)圖是否為樹(shù)

    摘要：只有一個(gè)連通分量還沒(méi)有環(huán)，就是樹(shù)，無(wú)根樹(shù)。無(wú)向圖邊的兩端是對(duì)稱(chēng)的，無(wú)向圖講究連通這個(gè)概念，沒(méi)有方向，沒(méi)有拓?fù)洌芟窦?，所以非常適合用并查集來(lái)解決。并查集寫(xiě)法參考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

    xbynet 評(píng)論0 收藏0

  • 261. Graph Valid Tree

    摘要：題目鏈接檢查圖的連通性及是否有環(huán)，可以，，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)來(lái)檢查是否有環(huán)。還可以用檢查是否有環(huán)，最后看的數(shù)量是否等于來(lái)判斷是不是。 261. Graph Valid Tree 題目鏈接：https://leetcode.com/problems... 檢查圖的連通性及是否有環(huán)，可以dfs，bfs，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)visited來(lái)檢查是否有環(huán)。...

    Jinkey 評(píng)論0 收藏0

  • leetcode310. Minimum Height Trees

    摘要：現(xiàn)在要求在這樣一棵生成樹(shù)中，找到生成樹(shù)的高度最低的所有根節(jié)點(diǎn)。然后利用鄰接表的相關(guān)屬性來(lái)判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。度數(shù)為一的頂點(diǎn)就是葉節(jié)點(diǎn)。這里使用異或的原因是對(duì)同一個(gè)值進(jìn)行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

    xiaoxiaozi 評(píng)論0 收藏0

  • 力扣(LeetCode)662

    摘要：每一層的寬度被定義為兩個(gè)端點(diǎn)該層最左和最右的非空節(jié)點(diǎn)，兩端點(diǎn)間的節(jié)點(diǎn)也計(jì)入長(zhǎng)度之間的長(zhǎng)度。示例輸入輸出解釋最大值出現(xiàn)在樹(shù)的第層，寬度為。因?yàn)?，這樣做的話(huà)時(shí)間復(fù)雜度是指數(shù)級(jí)別與樹(shù)的深度成指數(shù)關(guān)系。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)獲取這個(gè)樹(shù)的最大寬度。樹(shù)的寬度是所有層中的最大寬度。這個(gè)二叉樹(shù)與滿(mǎn)二叉樹(shù)（fu...

    MartinDai 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<