leetcode323. 无向图中连通分量的数目

曾经终败给现在 2023-07-07 05:46 33阅读 0赞

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例 1:

输入: n = 5 和 edges = \[\[0, 1\], \[1, 2\], \[3, 4\]\]

0 3  
| |  
1 --- 2 4

输出: 2  
示例 2:

输入: n = 5 和 edges = \[\[0, 1\], \[1, 2\], \[2, 3\], \[3, 4\]\]

0 4  
| |  
1 --- 2 --- 3

输出: 1  
注意:  
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，\[0, 1\] 与 \[1, 0\] 相同，所以它们不会同时在 edges 中出现。

思路：并查集，一直合并，最后查有几个根即可

class Solution {
        int[] parent;//这是记录关系的数组
        //查找
        int find(int parent[], int i) {
            if (parent[i] == -1)
                return i;
            return find(parent, parent[i]);
        }
        //合并
        void union(int parent[], int x, int y) {
            int xset = find(parent, x);
            int yset = find(parent, y);
            if (xset != yset)
                parent[xset] = yset;
        }
        public int countComponents(int n, int[][] edges) {
            int len=edges.length;
            parent = new int[n];
            Arrays.fill(parent, -1);
            for (int i = 0; i < len; i++) {
                union(parent, edges[i][0], edges[i][1]);
            }
            int count = 0;
            //查根的数量
            for (int i = 0; i < n; i++)
                if (parent[i] == -1)
                    count++;
            return count;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode323. 无向图中连通分量的数目

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。示例 1: 输入: n = 5 和 edge

曾经终败给现在/ 2023年07月07日 05:46/ 0 赞/ 34 阅读

相关有向图的强连通分量之Tarjan算法

描述： To prove two sets A and B are equivalent, we can first prove A is a subset of B, an

墨蓝/ 2022年08月26日 12:12/ 0 赞/ 249 阅读

相关有向图(6)--计算强连通分量的Kosaraju算法

Kosaraju算法 1.在给定的一幅有向图G中，使用DepthFirstOrder来计算他的反向图R的逆后序排列 2.在G中进行标准的深度优先搜索，但是要按照刚才计算得到

古城微笑少年丶/ 2022年08月18日 02:42/ 0 赞/ 210 阅读

相关 poj 3177 & 3352 【无向图双连通分量Tarjan】

题目：poj 3177 & 3352 题意：大概意思就是给你一个无向图，让你添加最少的边，让所有点都双连通。分析：双连通的定义就是任意两个点至少有两条

Bertha 。/ 2022年08月13日 15:47/ 0 赞/ 192 阅读

相关判断无向图G是否连通

判断无向图G是否连通 include "stdafx.h" include<vector> include<iostream> us

电玩女神/ 2022年08月02日 12:39/ 0 赞/ 182 阅读

相关图___求无向图连通分量个数

求无向图连通分量个数方法：基于DFS，从某一顶点出发遍历图，for循环，改变起始顶点，count计数。代码如下： void DFSTraverse(AL

青旅半醒/ 2022年07月16日 12:47/ 0 赞/ 242 阅读

相关图论：连通分量和强连通分量

1.连通图 1.1 顶点的连通性在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。 1.2 连通图在无向图G中，若

小鱼儿/ 2022年05月23日 10:27/ 0 赞/ 386 阅读

相关温习Algs4 (三):无向图, 搜索和连通分量

无向图, 搜索和连通分量无向图 Graph.java 搜索 Visitor.java Search.java 深

我会带着你远行/ 2022年04月12日 04:08/ 0 赞/ 242 阅读

相关 2、无向图的各连通分支

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2018

系统管理员/ 2022年04月02日 08:47/ 0 赞/ 243 阅读

相关连通图和连通分量

连通图和连通分量 1．顶点间的连通性　在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，[快看小说网][Link 1

桃扇骨/ 2021年11月02日 02:24/ 0 赞/ 457 阅读