算法整理-并查集和分治
标签：int cto friend i++ private parent solution vector style
1. FriendCycle
class Solution {
public:
int findCircleNum(vectorint>>& M) {
int len = M.size();
if (len == 0) return 0;
vectorint> parent(len, 0);
for (int i=0; i) {
parent[i] = i;
}
int count = len;
for (int i=0; i)
for (int j=i+1; j) {
if (M[i][j] == 1) {
int parent1 = findParent(i, parent);
int parent2 = findParent(j, parent);
if (parent1 != parent2) {
parent[parent2] = parent1;
count--;
}
}
}
return count;
}
private:
int findParent(int pos, vectorint> &parent){
if (parent[pos] == pos) return pos;
int root = findParent(parent[pos], parent);
parent[pos] = root;
return root;
}
};
算法整理-并查集和分治
标签：int cto friend i++ private parent solution vector style
原文地址：https://www.cnblogs.com/cookcoder-mr/p/11080041.html
评论