leetcode323. 无向图中连通分量的数目
5星 · 超过95%的资源 165 浏览量
2020-12-15
01:02:47
上传
评论
收藏 28KB PDF 举报 
leetcode323. 无向图中连通分量的数目无向图中连通分量的数目
给定编号从 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;
}
}
作者：一只大白兔兔兔兔兔
weixin_38699830
- 粉丝: 6
- 资源: 973
相关推荐
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论10
最新资源