547 省份数量
解法一:dfs
本题nxn矩阵可视作邻接矩阵,对其可以进行图论的dfs或bfs遍历,找出所有的连通分量
关键在于如果计算连通分量的个数:如果第i - 1次dfs遍历后仍有节点没有被遍历,说明其属于新的连通分量
class Solution {
private:
void dfs(vector<vector<int>>& isConnected, vector<bool>& isVisited, int idx){
for(int j = 0; j < isConnected[idx].size(); j++){
if(isConnected[idx][j] && !isVisited[j]){
isVisited[j] = true;
dfs(isConnected, isVisited, j);
}
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> isVisited(n, false);
int ans = 0;
for(int i = 0; i < n; i++){
// 遍历一遍后,如果第二遍还出现了没有遍历过的节点
// 说明出现新的连通分量
if(!isVisited[i]){
// 找出i对应的所有连通节点,对其标记
dfs(isConnected, isVisited, i);
// i没有被访问过,所以出现新的连通分量
ans++;
}
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(n^2)\),其中 n 是城市的数量。需要遍历矩阵 n 中的每个元素。
空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 visited 记录每个城市是否被访问过,数组长度是 n,递归调用栈的深度不会超过 n
解法二: bfs
与dfs类似,以每个节点bfs遍历一遍,如果遍历停止,说明其访问完所有相连的节点
遍历后还有未访问的节点,说明有新的连通分量
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> isVisited(n, false);
int ans = 0;
for(int i = 0; i < n; i++){
queue<int> q;
if(!isVisited[i]){
ans++;
q.push(i);
while(!q.empty()){
int idx = q.front();
q.pop();
for(int j = 0; j < n; j++){
if(isConnected[idx][j] && !isVisited[j]){
q.push(j);
isVisited[j] = true;
}
}
}
}
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(n^2)\),其中 n 是城市的数量。需要遍历矩阵 isConnected 中的每个元素。
空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 visited 记录每个城市是否被访问过,数组长度是 n,广度优先搜索使用的队列的元素个数不会超过 n。
解法三: 并查集
class Solution {
public:
int Find(vector<int>& p, int x) {
if (p[x] != x)
p[x] = Find(p, p[x]);
return p[x];
}
void Union(vector<int>& p, int x, int y) { p[Find(p, x)] = Find(p, y); }
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int m = isConnected[0].size();
vector<int> parent(n);
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < m; j++) {
if (isConnected[i][j])
Union(parent, i, j);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i)
ans++;
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(n^2logn)\),其中 n 是城市的数量。需要遍历矩阵 isConnected 中的所有元素,时间复杂度是 \(O(n^2)\),如果遇到相连关系,则需要进行 2 次查找和最多 1 次合并,一共需要进行 \(2n^2\)次查找和最多\(n^2\)次合并,因此总时间复杂度是$ O(2n^2logn^2 )=O(n^2logn)\(。这里的并查集使用了路径压缩,但是没有使用按秩合并,最坏情况下的时间复杂度是 \(O(n^2logn)\),平均情况下的时间复杂度依然是 \(O(n2α(n))\),其中 α 为阿克曼函数的反函数,\)α(n) $可以认为是一个很小的常数。
空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 parent 记录每个城市所属的连通分量的祖先。