森林与并查集

并查集

概念

• 集：集合
• 并：联通、合并
• 查：查找、判断
• Quick-Find算法：快速查找算法

按秩的快速合并Quick_Union

• 将一棵树作为另一棵树的子树
• 按秩（树的节点个数）进行优化比按树的高度进行合并好，节点少的做子树
• 合并判断复杂度：O(logN)，联通判断复杂度：O(logN)

快速查找Quick_find

• 查找父节点
• 路径压缩

结构定义

typedef struct UnionSet {
    int *father, *size;
    int n;
} UnionSet;

结构操作之初始化

UnionSet *init(int n) {
    UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
    u->father = (int *)malloc(sizeof(int) * (n + 1));
    u->size = (int *)malloc(sizeof(int) * (n + 1)); // 记录每棵树的节点个数
    for (int i = 1; i <= n; i++) { 
        u->father[i] = i;  //自己为一棵树
        u->size[i] = 1; // 只有自己一个节点
    }
    u->n = n;
    return u;
}

结构操作之查找

一般查找

int find(UnionSet *u, int x) {
    return u->father[x];
}

普通查找

int find(UnionSet *u, int x) {
    if (x == u->father[x]) return x;
    return find(u, u->father[x]);
}

路径压缩

int find(UnionSet *u, int x) {
    return x == u->father[x] ? u->father[x] : (u->father[x] = find(u, u->father[x]));
}

结构操作之合并

• 经过证明，按树的秩合并比按树的高度合并时间复杂度更低

一般合并

int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    for (int i = 1; i <= u->n; i++) {
        if (u->father[i] != fa) continue;
        u->father[i] = fb;
    }
    return 1;
}

普通合并

int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    u->father[fa] = fb;
    return 1;
}

按高度合并

int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    if (height[fa] > height[fb]) {
        u->color[fb] = fa;
        ++heigth[fb];
    } else {
        u->color[fa] = fb;
        ++heigth[fa];
    }
//    for (int i = 1; i <= u->n; i++) {
//        if (u->color[i] != color_a) continue;
//        u->color[i] = color_b;
//    }
    return 1;
}

按秩合并

int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    //默认fa记录节点数量是最多的； 
    if (u->size[fa] < u->size[fb]) swap(fa, fb);
    u->father[fb] = fa;
    u->size[fa] += u->size[fb];
    return 1;
}

代码演示

#include <stdio.h>
#include <stdlib.h>

#define swap(a, b) {\
    a ^= b; b ^= a; a ^= b;\
}

//按秩优化
 
typedef struct UnionSet {
    int *father, *size;
    int n;
} UnionSet;


UnionSet *init(int n) {
    UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
    u->father = (int *)malloc(sizeof(int) * (n + 1));
    u->size = (int *)malloc(sizeof(int) * (n + 1)); // 记录每棵树的节点个数
    for (int i = 1; i <= n; i++) { 
        u->father[i] = i;  //自己为一棵树
        u->size[i] = 1; // 只有自己一个节点
    }
    u->n = n;
    return u;
}

int find(UnionSet *u, int x) { //路径压缩
    return x == u->father[x] ? u->father[x] : (u->father[x] = find(u, u->father[x]));
}

int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    //默认fa记录节点数量是最多的； 
    if (u->size[fa] < u->size[fb]) swap(fa, fb);
    u->father[fb] = fa;
    u->size[fa] += u->size[fb];
    
//    u->father[fa] = fb;
    
//    for (int i = 1; i <= u->n; i++) {
//        if (u->father[i] != fa) continue;
//        u->father[i] = fb;
//    }
    return 1;
}

void clear(UnionSet *u) {
    if (u == NULL) return ;
    free(u->father);
    free(u);
    return ;
}

int main() {
    return 0;
}

练习题

Leetcode 128	Leetcode 130
Leetcode 200	Leetcode 547
Leetcode 684	Leetcode 685