首页 > 编程语言 > 详细

算法整理-并查集和分治

时间:2019-06-29 21:50:14      阅读:85      评论:0      收藏:0      [点我收藏+]

一. Friend Cycle

用一个数组存储root结点,采用压缩路径的方法,查找的时间复杂度为O(1), 合并的时间复杂度为O(1)

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int len = M.size();
        if (len == 0) return 0;
        vector<int> parent(len, 0);
        for (int i=0; i<len; i++) {
             parent[i] = i;
        }
        int count = len;
        for (int i=0; i<len; i++)
          for (int j=i+1; j<len; 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, vector<int> &parent){
        if (parent[pos] == pos) return pos;
        
        int root = findParent(parent[pos], parent);
        parent[pos] = root;
        return root;
        
    }

};

二.  逆序对

算法整理-并查集和分治

原文:https://www.cnblogs.com/cookcoder-mr/p/11107870.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!