Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
0 3
| |
1 --- 2 4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
0 4
| |
1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
这道题让我们求无向图中连通区域的个数,LeetCode中关于图Graph的题屈指可数,解法都有类似的特点,都是要先构建邻接链表Adjacency List来做。这道题的一种解法是利用DFS来做,思路是给每个节点都有个flag标记其是否被访问过,对于一个未访问过的节点,我们将结果自增1,因为这肯定是一个新的连通区域,然后我们通过邻接链表来遍历与其相邻的节点,并将他们都标记成已访问过,遍历完所有的连通节点后我们继续寻找下一个未访问过的节点,以此类推直至所有的节点都被访问过了,那么此时我们也就求出来了连通区域的个数。
解法一:
class Solution {
public:
int countComponents(int n, vector<pair<int, int> >& edges) {
int res = ;
vector<vector<int> > g(n);
vector<bool> v(n, false);
for (auto a : edges) {
g[a.first].push_back(a.second);
g[a.second].push_back(a.first);
}
for (int i = ; i < n; ++i) {
if (!v[i]) {
++res;
dfs(g, v, i);
}
}
return res;
}
void dfs(vector<vector<int> > &g, vector<bool> &v, int i) {
if (v[i]) return;
v[i] = true;
for (int j = ; j < g[i].size(); ++j) {
dfs(g, v, g[i][j]);
}
}
};
这道题还有一种比较巧妙的方法,不用建立邻接链表,也不用DFS,思路是建立一个root数组,下标和节点值相同,此时root[i]表示节点i属于group i,我们初始化了n个部分 (res = n),假设开始的时候每个节点都属于一个单独的区间,然后我们开始遍历所有的edge,对于一条边的两个点,他们起始时在root中的值不相同,这时候我们我们将结果减1,表示少了一个区间,然后更新其中一个节点的root值,使两个节点的root值相同,那么这样我们就能把连通区间的所有节点的root值都标记成相同的值,不同连通区间的root值不相同,这样也能找出连通区间的个数。
解法二:
class Solution {
public:
int countComponents(int n, vector<pair<int, int> >& edges) {
int res = n;
vector<int> root(n);
for (int i = ; i < n; ++i) root[i] = i;
for (auto a : edges) {
int x = find(root, a.first), y = find(root, a.second);
if (x != y) {
--res;
root[y] = x;
}
}
return res;
}
int find(vector<int> &root, int i) {
while (root[i] != i) i = root[i];
return i;
}
};
类似题目:
参考资料:
https://leetcode.com/discuss/77308/accepted-dfs-in-c
https://leetcode.com/discuss/77027/c-solution-using-union-find
https://leetcode.com/discuss/76519/similar-to-number-of-islands-ii-with-a-findroot-function
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数的更多相关文章
-
[LeetCode] 323. Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), ...
-
LeetCode Number of Connected Components in an Undirected Graph
原题链接在这里:https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ 题目: Giv ...
-
LeetCode 323. Number of Connected Components in an Undirected Graph
原题链接在这里:https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ 题目: Giv ...
-
323. Number of Connected Components in an Undirected Graph (leetcode)
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), ...
-
Number of Connected Components in an Undirected Graph -- LeetCode
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), ...
-
【LeetCode】323. Number of Connected Components in an Undirected Graph 解题报告 (C++)
作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 并查集 日期 题目地址:https://leetcod ...
-
[Swift]LeetCode323. 无向图中的连通区域的个数 $ Number of Connected Components in an Undirected Graph
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), ...
-
[Locked] Number of Connected Components in an Undirected Graph
Number of Connected Components in an Undirected Graph Given n nodes labeled from 0 to n - 1 and a li ...
-
323. Number of Connected Components in an Undirected Graph按照线段添加的并查集
[抄题]: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of n ...
随机推荐
-
DIY一个高大上带提醒的计时器,简单实用,你还在等什么
小编心语:锵锵锵!小编我又来了!昨天发了一篇比较实用的<Python聊天室>,鉴于反响还不错,SO ,小编也想给大家多分享点有用的干货,让大家边学边用.好了,闲话不多说,今天要给各位看官们 ...
-
纯手工打造漂亮的垂直时间轴,使用最简单的HTML+CSS+JQUERY完成100个版本更新记录的华丽转身!
前言 FineUI控件库发展至今已经有 5 个年头,目前论坛注册的QQ会员 5000 多人,捐赠用户 500 多人(捐赠用户转化率达到10%以上,在国内开源领域相信这是一个梦幻数字!也足以证明Fine ...
-
Visual Studio 2015 社区版.专业版.企业版[含安装密钥Pro&;Ent]
社区版(Visual Studio Community 2015)可供非企业或开源开发者们免费访问: 在线安装exe:http://download.microsoft.com/download/B/ ...
-
javascript中的表结构
列表是一种常见的数据结构,通常列表是一族有徐的数据,列表中的数据项称为元素.在javascript中列表中的数据可以是任意类型的,列表中可以保存多少元素没有事先限定,实际使用时元素的数量只收到程序内内 ...
-
mysql 数据备份还原
悲剧的一天,不小心将数据库删了... 命令行备份数据库 1.mysqldump命令进行备份.该命令将连接MySQL服务器并创建SQL转储文件,该文件包含了重新创建数据库所必需的所有SQL语句.该命令的 ...
-
dojo省份地市级联之地市封装类(二)
dojo省份地市级联之地市封装类 City.java: /** * 地市封装类 */ package com.you.model; import java.io.Serializable; /** * ...
-
java游戏开发杂谈 - 事件处理
大家都知道,游戏需要跟玩家交互,需要接收玩家的鼠标.键盘发出的命令,比如在地图上点击一下,人物就自动寻路走过去:键盘上按下某个键,就弹出一个背包界面. 这些逻辑是怎么处理的呢? 大家先不用深究太详细的 ...
-
java网络编程基本知识
1.基本概念 网络:一组相互连接的计算机,多台计算机组成,使用物理线路进行连接 网络连接的功能:交换数据.共享资源 网络编程3要素: IP 地址:唯一标识网络上的每一台计算机,两台计算机之间通信的必备 ...
-
[Swift]LeetCode374. 猜数字大小 | Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to gues ...
-
delphi提示“Undeclared identifier”TForm的缺少引用单元列表
在interface uses 添加TForms;