323. Number of Connected Components in an Undirect

zsy888 发布于2019-08-14 17:27 / 1606人阅读

摘要：题目链接这道题和是一个思路，一个初始化为，每次有新的就两个节点，如果两个节点原来不在一个连通图里面就减少并且连起来，如果原来就在一个图里面就不管。用一个索引来做，优化就是加权了，每次把大的树的当做，小的树的作为。

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

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

转载请注明本文地址：https://www.ucloud.cn/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