相关算法 合并的时间复杂度 查找的时间复杂度
Quick-Find算法 O(N) O(1)
Quick-Union算法 O(lgN)~O(N) O(lgN)~O(N)
Weighted按质优化 O(lgN) O(lgN)
路径压缩 ≈O(1) ≈O(1)

在实际工程中，可直接跳过按质优化采用路径压缩，时间效率上相差不大，但可以节省存储节点个数 (weight) 的内存消耗

Quick-Find

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

typedef struct UnionSet {
    int *flag;
    int n;
} UnionSet;

UnionSet *init(int n) {
    UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
    set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
    for (int i = 1; i <= n; i++) {
        set->flag[i] = i;
    }
    set->n = n;
    return set;
}

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

int find(UnionSet *set, int a) {
    return set->flag[a];
}

int merge(UnionSet *set, int a, int b) {
    if (find(set, a) == find(set, b)) return 0;
    int flag_b = set->flag[b];
    for (int i = 1; i <= set->n; i++) {
        if (set->flag[i] == flag_b) set->flag[i] = set->flag[a];
    }
    return 1;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    UnionSet *set = init(n);
    for (int i = 0; i < m; i++) {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        switch (op) {
            case 1:
                merge(set, a, b);
                break;
            case 2:
                printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
                break;
        }
    }
    clear(set);
    return 0;
}

Quick-Union

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

typedef struct UnionSet {
    int *flag; //记录父节点的编号
    int n;
} UnionSet;

UnionSet *init(int n) {
    UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
    set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
    for (int i = 1; i <= n; i++) {
        set->flag[i] = i;
    }
    set->n = n;
    return set;
}

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

int find(UnionSet *set, int a) {
    if (set->flag[a] == a) return a;
    return find(set, set->flag[a]);
    //return set->flag[a] = find(set, set->flag[a]); //路径压缩
}

int merge(UnionSet *set, int a, int b) {
    int flag_a = find(set, a);
    int flag_b = find(set, b);
    if (flag_a == flag_b) return 0;
    set->flag[flag_b] = flag_a;
    return 1;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    UnionSet *set = init(n);
    for (int i = 0; i < m; i++) {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        switch (op) {
            case 1:
                merge(set, a, b);
                break;
            case 2:
                printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
                break;
        }
    }
    clear(set);
    return 0;
}

Weighted Quick-Union

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

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

typedef struct UnionSet {
    int *flag; //记录父节点的编号
    int *node_num; //记录子集（包括自身）的节点数量
    int n;
} UnionSet;

UnionSet *init(int n) {
    UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
    set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
    set->node_num = (int *)malloc(sizeof(int) * (n + 1));
    for (int i = 1; i <= n; i++) {
        set->flag[i] = i;
        set->node_num[i] = 1;
    }
    set->n = n;
    return set;
}

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

int find(UnionSet *set, int a) {
    if (set->flag[a] == a) return a;
    return find(set, set->flag[a]);
    //return set->flag[a] = find(set, set->flag[a]); //路径压缩
}

int merge(UnionSet *set, int a, int b) {
    int fa = find(set, a);
    int fb = find(set, b);
    if (fa == fb) return 0;
    if (set->node_num[fb] > set->node_num[fa]) swap(fa, fb);
    set->flag[fb] = fa;
    set->node_num[fa] += set->node_num[fb];
    return 1;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    UnionSet *set = init(n);
    for (int i = 0; i < m; i++) {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        switch (op) {
            case 1:
                merge(set, a, b);
                break;
            case 2:
                printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
                break;
        }
    }
    clear(set);
    return 0;
}

可采用OJ上第71题的“朋友圈”进行测试

原文地址：http://www.cnblogs.com/Kelvin-Wu/p/16795309.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性