547. 省份数量

🟠   🔖  深度优先搜索 广度优先搜索 并查集 图  🔗 力扣 LeetCode

题目

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

题目大意

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入： isConnected = [[1,1,0],[1,1,0],[0,0,1]]

输出： 2

示例 2：

输入： isConnected = [[1,0,0],[0,1,0],[0,0,1]]

输出： 3

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

解题思路

这是一个 无向图 的连通分量问题，我们可以将每个城市看作图的一个节点，而 isConnected 是图的邻接矩阵：

1. 初始化一个布尔数组 visited，记录每个节点是否已经访问过。
2. 使用 深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 遍历图的每个节点 i：
   • 如果节点 i 未访问，启动一次 DFS/BFS 遍历。
   • 遍历过程中将所有与 i 相连的节点标记为已访问。
   • 每次启动一个新的遍历，表示发现一个新的省份，省份计数加 1。
3. 返回省份计数。

复杂度分析

• 时间复杂度： O(n^2)，邻接矩阵中共有 n^2 个元素，每个元素最多访问一次。
• 空间复杂度： O(n)。
  • DFS：O(n)，栈的递归深度。
  • BFS：O(n)，队列的最大长度。

代码

深度优先搜索（DFS）

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
	const n = isConnected.length;
	const visited = new Array(n).fill(false);
	let provinces = 0;

	const dfs = (i) => {
		visited[i] = true;
		for (let j = 0; j < n; j++) {
			if (isConnected[i][j] === 1 && !visited[j]) {
				dfs(j);
			}
		}
	};

	for (let i = 0; i < n; i++) {
		if (!visited[i]) {
			provinces++;
			dfs(i);
		}
	}

	return provinces;
};

广度优先搜索（BFS）

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
	const n = isConnected.length;
	const visited = new Array(n).fill(false);
	let provinces = 0;

	const bfs = (i) => {
		const queue = [i];
		while (queue.length) {
			const node = queue.shift();
			for (let j = 0; j < n; j++) {
				if (isConnected[node][j] === 1 && !visited[j]) {
					visited[j] = true;
					queue.push(j);
				}
			}
		}
	};

	for (let i = 0; i < n; i++) {
		if (!visited[i]) {
			provinces++;
			visited[i] = true;
			bfs(i);
		}
	}

	return provinces;
};

相关题目

题号	标题	题解	标签	难度	力扣
323	无向图中连通分量的数目 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
657	机器人能否返回原点	[✓]	字符串 模拟	🟢	🀄️ 🔗
734	句子相似性 🔒		数组 哈希表 字符串	🟢	🀄️ 🔗
737	句子相似性 II 🔒		深度优先搜索 广度优先搜索 并查集 3+	🟠	🀄️ 🔗
1101	彼此熟识的最早时间 🔒		并查集 数组 排序	🟠	🀄️ 🔗
2101	引爆最多的炸弹		深度优先搜索 广度优先搜索 图 3+	🟠	🀄️ 🔗