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

137 阅读 0 评论 91 点赞

我是靠谱客的博主唠叨大白，这篇文章主要介绍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 中出现。

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

复制代码

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
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;
    }
}