Number of Connected Components in an Undirected Graph

谁借莪１个温暖的怀抱￠ 2022-01-09 08:51 139阅读 0赞

1 public class Solution {
     2     private int[] parent;
     3     public int countComponents(int n, int[][] edges) {
     4         if (edges.length == 0) {
     5             return n;
     6         }
     7         parent = new int[n];
     8         for (int i = 0; i < n; i++) {
     9             parent[i] = i;
    10         }
    11         
    12         for (int i = 0; i < edges.length; i++) {
    13             int aIndex = findParent(edges[i][0]);
    14             int bIndex = findParent(edges[i][1]);
    15             
    16             if (aIndex > bIndex) {
    17                 parent[aIndex] = bIndex;
    18             } else if (bIndex > aIndex) {
    19                 parent[bIndex] = aIndex;
    20             }
    21         }
    22         
    23         int result = 0;
    24         for (int i = 0; i < n; i++) {
    25             if (parent[i] == i) {
    26                 result++;
    27             }
    28         } 
    29         return result;
    30     }
    31     
    32     private int findParent(int x) {
    33         while (x != parent[x]) {
    34             parent[x] = parent[parent[x]];
    35             x = parent[x];
    36         }
    37         return x;
    38     }
    39 }

转载于:https://www.cnblogs.com/shuashuashua/p/5634710.html

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 Tensor is not an element of this graph 解决方法

问题描述：有两个模型，单独运行两个模型的pipeline时没有问题，但是封装到flask服务后报了如下错误： ![在这里插入图片描述][watermark_type_

落日映苍穹つ/ 2022年09月10日 11:13/ 0 赞/ 108 阅读

相关 HDU 5333 Undirected Graph【LCT+BIT】

LCT：每次操作相当于只把区间\[L,R\]之间的边连起来，求联通分量的个数。思路：把操作排序后，对于区间\[L,R\]的操作，先把R所有v<R的边(R→v)

àì夳堔傛蜴生んèń/ 2022年08月04日 05:26/ 0 赞/ 143 阅读

相关 434_Number_of_Segments_in_a_String

/ Count the number of segments in a string, where a segment is defined to be a c

朴灿烈づ我的快乐病毒、/ 2022年06月08日 00:51/ 0 赞/ 142 阅读

相关 448. Find All Numbers Disappeared in an Array

[原题链接][Link 1] 这个题主要是寻找没有出现的数字。代码的主要思路是，如果找到数值i，则把对应i-1索引的值取负。之后遍历列表，如果发现i-1里面的数>

秒速五厘米/ 2022年06月02日 09:22/ 0 赞/ 160 阅读

相关 448. Find All Numbers Disappeared in an Array

> Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), > some elements

Love The Way You Lie/ 2022年06月01日 00:23/ 0 赞/ 199 阅读

相关 [LintCode] Find the Connected Component in the Undirected Graph

[Find the Connected Component in the Undirected Graph][] Find the number connected comp

雨点打透心脏的1/2处/ 2022年03月29日 06:45/ 0 赞/ 127 阅读

相关 A component is changing an uncontrolled input of type number to be controlle react报错

react 报错 A component is changing an uncontrolled input of type number to be controll

约定不等于承诺〃/ 2022年03月25日 02:59/ 0 赞/ 157 阅读

相关 Number of Connected Components in an Undirected Graph

1 public class Solution { 2 private int[] parent; 3 public int cou

谁借莪１个温暖的怀抱￠/ 2022年01月09日 08:51/ 0 赞/ 140 阅读

相关 Connected Graph

[Connected Graph][] 求n个点的无向联通图数量，\\(n\\leq 50\\)。解直接无向联通图做状态等于是以边点做考虑，难以去重，考虑联通对立

我不是女神ヾ/ 2022年01月08日 00:29/ 0 赞/ 225 阅读

相关 448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), some elements appea

r囧r小猫/ 2021年10月01日 07:30/ 0 赞/ 219 阅读