323. Number of Connected Components in an Undirect

zsy888 發布于2019-08-14 17:27 / 1607人閱讀

摘要：題目鏈接這道題和是一個思路，一個初始化為，每次有新的就兩個節點，如果兩個節點原來不在一個連通圖里面就減少并且連起來，如果原來就在一個圖里面就不管。用一個索引來做，優化就是加權了，每次把大的樹的當做，小的樹的作為。

323. Number of Connected Components in an Undirected Graph

題目鏈接：https://leetcode.com/problems...

這道題和numbers of islands II 是一個思路，一個count初始化為n，union find每次有新的edge就union兩個節點，如果兩個節點(u, v)原來不在一個連通圖里面就減少count并且連起來，如果原來就在一個圖里面就不管。用一個索引array來做，union find優化就是加權了，每次把大的樹的root當做parent，小的樹的root作為child。

public class Solution {
    public int countComponents(int n, int[][] edges) {
        // union find
        int count = n;
        // array to store parent
        init(n, edges);
        for(int[] edge : edges) {
            int root1 = find(edge[0]);
            int root2 = find(edge[1]);
            if(root1 != root2) {
                union(root1, root2);
                count--;
            }
        }
        return count;
    }
    
    int[] map;
    private void init(int n, int[][] edges) {
        map = new int[n];
        for(int[] edge : edges) {
            map[edge[0]] = edge[0];
            map[edge[1]] = edge[1];
        }
    }
    
    private int find(int child) {
        while(map[child] != child) child = map[child];
        return child;
    }
    
    private void union(int child, int parent) {
        map[child] = parent;
    }
}

云服務器 GPU云服務器 Connected Components styled-components web-components

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66652.html

Union-Find并查集算法學習筆記

摘要：算法鏈接學習工具，，環境搭建在小伙伴的推薦下，這個學期開始上普林斯頓的算法課。一系列的整數對代表與相互連接，比如等，每一個整數代表了一個。我覺得這個可能也是并查集相關應用。這學期繼續學習深入理解了就能明白了。《算法》鏈接：1.5 Case Study: Union-Find學習工具：mac，java8，eclipse,coursera 環境搭建在小伙伴的推薦下，這個學期開始上普林斯頓...

hzc 2019-08-14 17:08 評論0 收藏0
【Change Detection系列一】$digest 在Angular新版本中重生

摘要：感謝您的閱讀如果喜歡這篇文章請點贊。它對我意義重大，它能幫助其他人看到這篇文章。對于更高級的文章，你可以在或上跟隨我。 I’ve worked with Angular.js for a few years and despite the widespread criticism I think this is a fantastic framework. I’ve started w...

legendaryedu 2019-08-21 17:59 評論0 收藏0
Find the Connected Component in the Undirected Gra

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a...

Benedict Evans 2019-08-14 17:07 評論0 收藏0