2685-统计完全连通分量的数量

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges
其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。

返回图中 完全连通分量 的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。

如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。

示例 1：

![](https://assets.leetcode.com/uploads/2023/04/11/screenshot-
from-2023-04-11-23-31-23.png)

**输入：** n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
**输出：** 3
**解释：** 如上图所示，可以看到此图所有分量都是完全连通分量。

示例 2：

![](https://assets.leetcode.com/uploads/2023/04/11/screenshot-
from-2023-04-11-23-32-00.png)

**输入：** n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
**输出：** 1
**解释：** 包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

提示：

  • 1 <= n <= 50
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 不存在重复的边

下午两点【biIibiIi@灵茶山艾府】 直播讲题，记得关注哦~

DFS 每个连通块，统计当前连通块的点数 v 和边数 e。

  • 每访问一个点，就把 v 加一。
  • e 加上点 v 的邻居个数。注意这样一条边会统计两次。

在完全图中，任意两点之间都有边，相当于从 v 个点中选 2 个点的方案数。所以有

e = \dfrac{v(v-1)}{2}

由于上面统计的时候，一条边统计了两次，所以代码中的判断条件是

e = v(v-1)

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        vis = [False] * n
        def dfs(x: int) -> None:
            vis[x] = True
            nonlocal v, e
            v += 1
            e += len(g[x])
            for y in g[x]:
                if not vis[y]:
                    dfs(y)

        ans = 0
        for i, b in enumerate(vis):
            if not b:
                v = e = 0
                dfs(i)
                ans += e == v * (v - 1)
        return ans
[sol1-Java]
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
31
32
33
34
35
36
37
class Solution {
    private List<Integer>[] g;
    private boolean vis[];
    private int v, e;

    public int countCompleteComponents(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
        }

        int ans = 0;
        vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                v = 0;
                e = 0;
                dfs(i);
                if (e == v * (v - 1))
                    ans++;
            }
        }
        return ans;
    }

    private void dfs(int x) {
        vis[x] = true;
        v++;
        e += g[x].size();
        for (var y : g[x])
            if (!vis[y])
                dfs(y);
    }
}
[sol1-C++]
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
31
32
class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>> &edges) {
        vector<vector<int>> g(n);
        for (auto &e: edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x); // 建图
        }

        vector<int> vis(n);
        int ans = 0, v, e;
        function<void(int)> dfs = [&](int x) {
            vis[x] = true;
            v++;
            e += g[x].size();
            for (int y: g[x])
                if (!vis[y])
                    dfs(y);
        };

        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                v = 0;
                e = 0;
                dfs(i);
                ans += e == v * (v - 1);
            }
        }
        return ans;
    }
};
[sol1-Go]
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
31
func countCompleteComponents(n int, edges [][]int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	vis := make([]bool, n)
	var v, e int
	var dfs func(int)
	dfs = func(x int) {
		vis[x] = true
		v++
		e += len(g[x])
		for _, y := range g[x] {
			if !vis[y] {
				dfs(y)
			}
		}
	}
	for i, b := range vis {
		if !b {
			v, e = 0, 0
			dfs(i)
			if e == v*(v-1) {
				ans++
			}
		}
	}
	return
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n+m)，其中 m 为 edges 的长度。
  • 空间复杂度：\mathcal{O}(n+m)。
 Comments
On this page
2685-统计完全连通分量的数量