并查集

1.定义

合并：合并两个集合。
查找：判断两个元素是否在一个集合。

使用father[i]表示元素i的父亲结点。如果father[i] = i，则i是根结点。

2.基本操作

#include <cstdio>

const int maxn = 110;

int father[maxn];
int n;

//初始化
void init() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//寻找x的根结点（路径压缩）
int findFather(int x) {
    int temp = x;//先保存一下原先的x
    while (x != father[x]) {
        x = father[x];
    }
    //此时x存放的是根结点，下面把路径上所有结点的father改为根结点
        while (temp != father[temp]) {
            int z = temp;
            temp = father[temp];
            father[z] = x;
        }
    return x;
}

//合并
void merge(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

int main() {
    scanf("%d", &n);
    init();
}

例1

#include <cstdio>

const int maxn = 110;

int father[maxn];
bool isRoot[maxn];
int n, m;

//初始化
void init() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//寻找x的根结点（路径压缩）
int findFather(int x) {
    int temp = x;//先保存一下原先的x
    while (x != father[x]) {
        x = father[x];
    }
     //此时x存放的是根结点，下面把路径上所有结点的father改为根结点
        while (temp != father[temp]) {
            int z = temp;
            temp = father[temp];
            father[z] = x;
        }
    return x;
}

//合并
void merge(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    int a, b;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    for (int i = 1; i <= n; i++) {
        isRoot[findFather(i)] = true;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (isRoot[i] == true) {
            res++;
        }
    }
    printf("%d\n", res);
}

1107 Social Clusters