并查集的应用,即同一个province的节点可以在同一集合中
题意ref{:target=”_blank”}
并查集模板{:target=”_blank”}
C++ 代码
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
p_ = vector<int>(n);
// 初始化,每个节点的祖宗节点是自己
for(int i=0; i<n; ++i)p_[i] = i;
for(int i=0; i<n; ++i) {
for(int j=i+1; j<n; ++j) {
if(isConnected[i][j]) merge(i, j);
}
}
int res = 0;
// 统计集合个数
for(int i=0; i<n; ++i)if(p_[i] == i)res++;
return res;
}
private:
vector<int> p_;
// 查找x节点的祖宗节点
int find(int x) {
if(p_[x] != x) {
p_[x] = find(p_[x]);
}
return p_[x];
}
// 合并2个同一集合的节点
void merge(int x, int y) {
int fa = find(x), fb = find(y);
p_[fa] = fb;
}
};