LeetCode刷题实战547：省份数量
共 2343字，需浏览 5分钟
·
2022-03-10 17:14
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.
示例
解题
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int res = 0;
// 记录已访问城市
Listvisited = new ArrayList<>();
// 记录路径
Queuequeue = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 未访问城市入队
if (!visited.contains(i)) {
queue.offer(i);
while (!queue.isEmpty()) {
int cur = queue.poll();
// 当前城市已访问
visited.add(cur);
// 寻找连接城市
for (int j = 0; j < n; j++) {
if (isConnected[cur][j] == 1 && !visited.contains(j)) {
// 连接城市入队
queue.offer(j);
}
}
}
res++;
}
}
return res;
}
}