并查集

1. 概述

并查集用来解决图的连通性问题，并查集的方法首先要为每一个点建立集合，
接着写出判断两个点是否属于一个集合的方式，最后不断合并集合

  • Union -- 连接两个节点
  • Find -- 查找所属的连通分量
    所以，并查集主要就是实现以下接口
class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
    
    /* 返回当前节点的根节点 */
    private int find(int x);
}

为了便于描述连通状态（同时使图的关系可以用数组存储）
让同属一个连通域的元素指向同一根节点
这里可以用数组parent[]表示这种关系

  • 如果自己就是根节点，那么 parent[i] = i，即自己指向自己
  • 如果自己不是根节点，则 parent[i] = root 指向根节点索引
private int count;
private int[] parent;
// 构造函数
public UF (int n) {
    this.count = n; //集合总数
    parent = new int[n]; //初始化指针（索引）
    for (int i = 0; i < n; i++) {
        // 最初，每个节点均是独立的
        parent[i] = i; //每个节点指针指向自己
    }
}

Union 方法

// 伪代码
public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) return;
    parent[rootP] = rootQ; //集合p合并到集合q中
    count--;//连通域减一
}

Find方法（路径压缩后）

private int find(int x) {
    while (x != parent[x]) {//遍历求根节点
        parent[x] = parent[parent[x]];//重构节点，其实该操作只会进行一次，因为每次合并都会更新，不会使高度过深
        x = parent[x];}
    return x;
}

private int find(int x) {
    if(parent[x]==x) reuturn x;
    parent[x] = find(parent[x]);//递归求根节点，同时重构该集合，减少之后查找次数
    return parent[x];
}

2. 最长连续序列

最长连续序列 
class Solution {
public:
    unordered_map series;//指针关系
    unordered_map count;//用于合并时计数
    int max_ = 1;
    int longestConsecutive(vector& nums) {
       if(nums.size()==0) return 0;
       for(int num:nums){
            series[num]=num;//每个数建立一个集合
            count[num]=1;//初始值为1
            }
        for(int i = nums.size()-1; i>=0; i--)
            if(series.count(nums[i]+1))   union_(nums[i]);

        return max_;
    }
    void union_(int num){
        int right1 = find(num);
        int right2 = find(num+1);
        if(right1==right2) return;
        series[num]=right2;//合并集合
        count[right2]=count[right1]+count[right2];//合并计数
        max_ = max(max_,count[right2]);//记录最大值
    }
    int find(int num){
        if(series[num]==num) return num;
        series[num] = find(series[num]);//压缩路径
        return series[num];
    }
};

3. 岛屿数量

岛屿数量 
class Solution {
public:
    vector parent;
    int sum;
    int numIslands(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int index;
        //初始化parent数组，记录初始岛屿数量
        for (int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                index = i * n + j;
                parent.push_back(index);//后面根据索引建立集合簇
                if(grid[i][j] == '1')
                    sum++;  //记录初始岛屿数量
            }
        
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++){
                index = i * n + j;  //从左往右，从上往下遍历合并全部岛屿
                if (grid[i][j] == '1') {
                    if (i+1 < m && grid[i+1][j] == '1') { //下
                        unions(index, (i + 1) * n + j);
                    }
                    if (j+1
经典算法

相关

十大经典算法-冒泡排序及优化方法（java实现）

标签