题面描述

题目要求计算一个无向图的连通块数量。输入包含两个整数 n 和 m，分别表示图中点的数量和边的数量，接着是 m 行，每行两个整数 u 和 v，表示点 u 和点 v 之间的无向边。输出应为该图的连通块数。示例输入为 4（点数）、1（边数）和边 0 1，输出为 3，表示图中共有 3 个连通块。

思路

并查集裸题，每次加边直接并查集合并，判断连通块的时候可以使用fa[i]是不是原来初始化时候设置的值。

1. 初始化一个大小为 n 的数组 fa，每个元素初始为其自身，表示每个点自成一个连通块。
2. 通过 Un 函数将输入的边连接的两个点合并在同一个连通块中。
3. 通过遍历 fa 数组，统计根节点（即初始化时的节点值）数量，从而得到连通块的数量。

具体步骤：

• 输入点的数量 n 和边的数量 m。
• 对于每条边，通过并查集的合并操作将两个节点连接起来。
• 最后遍历 fa 数组，统计不同的根节点数目，即为连通块的数量。

代码

C++

#include<bits/stdc++.h>

using namespace std;

const int M = 205;  // 定义常量 M，表示最大节点数
int fa[M];  // 用于存储并查集的父节点

// 初始化并查集，将每个节点的父节点设为其自身
inline void init() { 
    for (int i = 0; i < M; i++) 
        fa[i] = i; 
}

// 查找节点 x 的根节点，并进行路径压缩
int findfa(int x) {
    return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}

// 合并两个节点 a 和 b 所在的集合
void Un(int a, int b) {
    int fa1 = findfa(a);  // 查找 a 的根节点
    int fa2 = findfa(b);  // 查找 b 的根节点
    if (fa1 != fa2) 
        fa[fa1] = fa2;  // 将 fa1 的根节点指向 fa2，完成合并
}

int main() {
    init();  // 初始化并查集
    int n, m, u, v;  // 定义点数 n、边数 m 以及每条边的两个端点 u 和 v
    cin >> n >> m;  // 输入点数和边数
    for (int i = 1; i <= m; i++) {  // 遍历每一条边
        cin >> u >> v;  // 输入边的两个端点
        Un(u, v);  // 合并两个端点
    }
    
    int ans = 0;  // 用于统计连通块的数量
    for (int i = 0; i < n; i++) 
        ans += (fa[i] == i);  // 统计根节点的数量，即连通块的数量

    cout << ans << endl;  // 输出连通块的数量    
    return 0;  // 程序结束
}

java

import java.util.Scanner;

public class Main {
    static final int M = 205; // 定义常量 M，表示最大节点数
    static int[] fa = new int[M]; // 用于存储并查集的父节点数组

    // 初始化并查集，将每个节点的父节点设为其自身
    static void init() {
        for (int i = 0; i < M; i++) {
            fa[i] = i; // 初始化时每个节点的父节点是其自身
        }
    }

    // 查找节点 x 的根节点，并进行路径压缩
    static int findfa(int x) {
        return x == fa[x] ? x : (fa[x] = findfa(fa[x])); // 如果 x 是根节点，返回 x，否则递归查找其父节点
    }

    // 合并两个节点 a 和 b 所在的集合
    static void Un(int a, int b) {
        int fa1 = findfa(a); // 查找 a 的根节点
        int fa2 = findfa(b); // 查找 b 的根节点
        if (fa1 != fa2) { // 如果 a 和 b 不在同一个集合
            fa[fa1] = fa2; // 将 fa1 的根节点指向 fa2，完成合并
        }
    }

    public static void main(String[] args) {
        init(); // 初始化并查集
        Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象以读取输入
        int n = scanner.nextInt(); // 输入点数 n
        int m = scanner.nextInt(); // 输入边数 m
        for (int i = 1; i <= m; i++) { // 遍历每一条边
            int u = scanner.nextInt(); // 输入边的一个端点 u
            int v = scanner.nextInt(); // 输入边的另一个端点 v
            Un(u, v); // 合并两个端点所在的集合
        }
        int ans = 0; // 用于统计连通块的数量
        for (int i = 0; i < n; i++) { // 遍历每个节点
            if (fa[i] == i) { // 如果节点 i 是根节点
                ans++; // 统计根节点的数量，即连通块的数量
            }
        }
        System.out.println(ans); // 输出连通块的数量
    }
}

python

def init():
    global fa  # 声明 fa 为全局变量
    fa = list(range(M))  # 初始化 fa 数组，每个节点的父节点指向自身

def findfa(x):
    # 查找节点 x 的根节点，并进行路径压缩
    if x == fa[x]:
        return x  # 如果 x 是根节点，返回 x
    fa[x] = findfa(fa[x])  # 递归查找父节点，同时进行路径压缩
    return fa[x]  # 返回根节点

def Un(a, b):
    # 合并两个节点 a 和 b 所在的集合
    fa1 = findfa(a)  # 查找 a 的根节点
    fa2 = findfa(b)  # 查找 b 的根节点
    if fa1 != fa2:  # 如果 a 和 b 不在同一个集合
        fa[fa1] = fa2  # 将 fa1 的根节点指向 fa2，完成合并

M = 205  # 定义常量 M，表示最大节点数
init()  # 初始化并查集
n = int(input())  # 输入点数 n
m = int(input())  # 输入边数 m
for i in range(1, m + 1):  # 遍历每一条边
    u, v = map(int, input().split())  # 输入边的两个端点 u 和 v
    Un(u, v)  # 合并两个端点所在的集合
ans = 0  # 用于统计连通块的数量
for i in range(n):  # 遍历每个节点
    if fa[i] == i:  # 如果节点 i 是根节点
        ans += 1  # 统计根节点的数量，即连通块的数量
print(ans)  # 输出连通块的数量