资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/323. Number of Connected Components in an Undirect

323. Number of Connected Components in an Undirect

zsy888 / 1678人阅读

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

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。

</>复制代码 
  1. public class Solution {
  2.     public int countComponents(int n, int[][] edges) {
  3.         // union find
  4.         int count = n;
  5.         // array to store parent
  6.         init(n, edges);
  7.         for(int[] edge : edges) {
  8.             int root1 = find(edge[0]);
  9.             int root2 = find(edge[1]);
  10.             if(root1 != root2) {
  11.                 union(root1, root2);
  12.                 count--;
  13.             }
  14.         }
  15.         return count;
  16.     }
  17.     
  18.     int[] map;
  19.     private void init(int n, int[][] edges) {
  20.         map = new int[n];
  21.         for(int[] edge : edges) {
  22.             map[edge[0]] = edge[0];
  23.             map[edge[1]] = edge[1];
  24.         }
  25.     }
  26.     
  27.     private int find(int child) {
  28.         while(map[child] != child) child = map[child];
  29.         return child;
  30.     }
  31.     
  32.     private void union(int child, int parent) {
  33.         map[child] = parent;
  34.     }
  35. }
云服务器 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 评论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 评论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 评论0 收藏0

发表评论

登陆后可评论

0条评论

zsy888

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<