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

🟠 🔖 深度优先搜索 广度优先搜索 图 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi.

Return the number ofcomplete connected components of the graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

A connected component is said to be complete if there exists an edge between every pair of its vertices.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: From the picture above, one can see that all of the components of this graph are complete.

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.

Constraints:

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
There are no repeated edges.

题目大意

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

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

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

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

示例 1：

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

示例 2：

输入： 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
不存在重复的边

解题思路

构建图：
- 使用邻接表 graph 表示图结构，graph[a] 存储与节点 a 相邻的节点列表。
DFS 遍历：
- 对每个未访问的节点 i 进行 DFS 遍历，找到当前的连通分量 component。
- DFS 过程中：
  - component 记录当前连通分量内的所有节点。
  - visited 集合记录已访问的节点，避免重复遍历。
检查是否为完全图：
- 对于一个连通分量 component：
  - 完全图性质：对于每个节点 node，应有 graph[node] 的邻居数量 == component.size - 1。
  - 如果所有节点都满足上述条件，则该连通分量为完全图。
统计满足条件的连通分量数量。

复杂度分析

时间复杂度：O(n + m)。
- 遍历每个节点 O(n)。
- DFS 遍历所有边 O(m)。
- 对每个连通分量进行完全性检查，最差情况 O(n)。
空间复杂度：O(n + m)。
- graph 邻接表存储 m 条边：O(m)。
- visited 和 component 集合最差情况 O(n)。

代码

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countCompleteComponents = function (n, edges) {
	let graph = {};

	// 构建图
	for (let [a, b] of edges) {
		if (!graph[a]) {
			graph[a] = [];
		}
		if (!graph[b]) {
			graph[b] = [];
		}
		graph[a].push(b);
		graph[b].push(a);
	}

	let visited = new Set();
	let count = 0;

	// 遍历每个节点，查找连通分量
	for (let i = 0; i < n; i++) {
		if (!visited.has(i)) {
			let component = new Set();
			dfs(i, component, visited);

			// 判断该连通分量是否是完全图
			if (
				[...component].every(
					(node) => (graph[node] || []).length === component.size - 1
				)
			) {
				count++;
			}
		}
	}

	return count;

	// DFS 遍历
	function dfs(node, component, visited) {
		component.add(node);
		visited.add(node);
		for (let neighbor of graph[node] || []) {
			if (!visited.has(neighbor)) {
				dfs(neighbor, component, visited);
			}
		}
	}
};

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

# 2685. 统计完全连通分量的数量

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目