算法整理-并查集和分治
标签：enum circle 算法整理 时间复杂度 算法 end solution ++ root
一. Friend Cycle
用一个数组存储root结点，采用压缩路径的方法，查找的时间复杂度为O(1)， 合并的时间复杂度为O(1)
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;
}
};
二. 逆序对
算法整理-并查集和分治
标签：enum circle 算法整理 时间复杂度 算法 end solution ++ root
原文地址：https://www.cnblogs.com/cookcoder-mr/p/11107870.html
评论