- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode-cn.com/problems/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), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 1
Note:
Youcan 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.
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。
看到求联通分量的题,一般都可以用并查集。比如1101. The Earliest Moment When Everyone Become Friendsopen in new window。
只要把并查集背下来,这个题目基本直接写上去就好了。
C++代码如下:
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
map_ = vector<int>(n, 0);
components = n;
for (int i = 0; i < n; ++i) {
map_[i] = i;
}
for (vector<int>& edge : edges) {
uni(edge[0], edge[1]);
}
return components;
}
int find(int a) {
if (a == map_[a])
return a;
return find(map_[a]);
}
void uni(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb)
return;
map_[pa] = pb;
components --;
}
private:
vector<int> map_;
int components;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我是一名优秀的程序员,十分优秀!