一、思路概要与知识要点

并查集本身是一个经典的数据结构，核心在于①路径压缩和②按秩（数的高度）合并这两个优化技术。路径压缩可以减少查找父节点的深度（尽量要其变矮），而按秩合并可以避免树的深度过大（让数尽量变宽）。这两个优化点是实现高效并查集的关键。

算法的核心：

先设计一个结构体来存储每个节点的父节点和秩（树的高度）

用户交互界面：

如何让程序能够动态接收用户输入，比如节点的数量、节点的合并操作等

设计一个循环菜单，让用户可以选择初始化并查集、进行合并操作、查询两个节点是否属于同一集合等。

❗❗❗交互界面需要清晰易用，同时避免用户输入错误导致程序崩溃，因此需要加入输入验证。

可视化展示：

考虑到 C 语言的限制，可以在用户每次执行操作后，打印出当前的父节点数组和秩数组，这样用户可以直观地看到并查集的状态变化。 还可以在合并操作成功时，提示用户哪些节点被成功连接。

二、代码部分

1.并查集元素结构体

结构体定义 ：typedef struct 定义了一个名为 DisjointSet 的结构体类型。

这个结构体包含两个成员变量：

parent 用于存储当前节点的父节点

rank 用于存储当前节点所在树的高度（在按秩合并的优化策略中有用）

全局指针变量声明 ：DisjointSet *parentArray;

声明了一个指向 DisjointSet 类型的指针变量 parentArray。

这个指针用于指向存储所有并查集元素的动态分配的内存空间。初始时，它是一个未初始化的空指针，需要在后续的初始化函数中为其分配合适的内存。

全局整型变量声明 ：int size = 0;

声明了一个整型变量 size，用于记录当前并查集中元素的数量。初始值为 0，后续在初始化时会根据用户输入的元素数量进行赋值。

2.初始化并查集

函数定义与参数 ：void initialize(int n)

定义了一个名为 initialize 的函数，返回值类型为 void（无返回值），它接收一个整型参数 n，表示要初始化的并查集元素的数量。

内存分配 ：parentArray = (DisjointSet*)malloc(n * sizeof(DisjointSet));

使用 malloc 函数为 parentArray 指针分配内存空间。分配的内存空间大小为 n 乘以 DisjointSet 结构体的大小，这样可以存储 n 个 DisjointSet 类型的元素。

内存分配检查 ：if (parentArray == NULL)

判断内存分配是否成功。如果内存分配失败，malloc 会返回 NULL，此时程序输出 “内存分配失败！” 的提示信息，并调用 exit(EXIT_FAILURE) 函数终止程序的运行。

这是为了防止后续代码中使用未正确分配内存的指针而导致程序崩溃或出现其他不可预知的错误。

元素初始化循环 ：for (int i = 0; i < n; i++)

是一个 for 循环，循环变量 i 从 0 开始，依次递增，直到 i 等于 n - 1 时结束循环。这个循环的作用是遍历 parentArray 中的每个元素，并进行初始化操作。
                              parentArray[i].parent = i;：

将每个元素的父节点初始化为自身，表示每个元素一开始都属于一个独立的集合。
                              parentArray[i].rank = 1;：

将每个元素所在树的高度（秩）初始化为 1，因为在初始状态下，每个元素可以看作是一个高度为 1 的树。

更新并查集大小 ：size = n;

将全局变量 size 的值设置为 n，用于记录当前并查集中元素的数量。

3. 查函数

函数定义与参数 ：int find(int x)

定义了一个名为 find 的函数，返回值类型为 int，它接收一个整型参数 x，表示要查找的元素的索引。

查找根节点判断 ：if (parentArray[x].parent != x)

判断当前元素的父节点是否是它自身。如果不是，说明当前元素不是根节点，需要继续向上查找其父节点的父节点。

递归查找与路径压缩 ：在 if 条件成立时，parentArray[x].parent = find(parentArray[x].parent); 这行代码执行了两个主要操作：

递归查找父节点的根节点 ：find(parentArray[x].parent)

递归地调用 find 函数，查找当前元素父节点的根节点。

路径压缩 ：将当前元素的父节点直接更新为找到的根节点。这样，在后续对该元素的查找操作中，可以直接一步到达根节点，无需再经过中间的路径节点，从而缩短了查找路径，提高了效率。

返回根节点 ：return parentArray[x].parent;

返回当前元素的根节点。如果当前元素本身就是根节点（即 parentArray[x].parent == x），则直接返回自身；否则返回经过路径压缩后更新的父节点，即根节点

4. 并操作

函数定义与参数 ：void unionSets(int x, int y)

定义了一个名为 unionSets 的函数，返回值类型为 void，它接收两个整型参数 x 和 y，表示要合并的两个元素的索引。

查找根节点 ：int xRoot = find(x); 和 int yRoot = find(y);

分别调用 find 函数查找元素 x 和 y 所在集合的根节点。这是因为在合并两个集合之前，需要先找到它们各自的根节点，以便进行后续的合并操作。

检查是否已是同一集合 ：if (xRoot == yRoot) { return; }

判断两个元素是否已经在同一个集合中。如果是，直接返回，无需进行任何合并操作。这一步的目的是避免不必要的合并操作，提高程序的效率。

按秩合并判断 ：接下来的三个条件语句用于根据两个根节点的秩（树的高度）来决定如何合并两个集合。
① if (parentArray[xRoot].rank < parentArray[yRoot].rank)：

如果 xRoot 所在树的秩小于 yRoot 所在树的秩，则将 xRoot 的父节点设置为 yRoot。这样，较矮的树被合并到较高的树上，不会增加树的高度。
② else if (parentArray[xRoot].rank > parentArray[yRoot].rank)：

如果 xRoot 所在树的秩大于 yRoot 所在树的秩，则将 yRoot 的父节点设置为 xRoot。同样，这不会增加树的高度。
③else：

如果两棵树的秩相等，则将 yRoot 的父节点设置为 xRoot（也可以反过来），并将 xRoot 的秩增加 1。因为两棵树高度相同，合并后树的高度会增加 1。

5.显示函数

函数定义 ：void display()

定义了一个名为 display 的函数，返回值类型为 void，表示该函数不返回任何值。它没有参数，因为要显示的是全局的并查集状态。

输出表头信息 ：printf("\n元素\t父节点\t秩\n");

这行代码输出了一行表头信息，用于标识后续输出数据的含义。其中，\n 表示换行，\t 表示水平制表符，用于对齐输出内容，使输出格式更加整齐美观。

循环输出每个元素的状态 ：for (int i = 0; i < size; i++)

是一个 for 循环，循环变量 i 从 0 开始，依次递增，直到 i 等于 size - 1 时结束循环。这里的 size 是一个全局变量，表示并查集中元素的数量。

printf("%d\t%d\t%d\n", i, parentArray[i].parent, parentArray[i].rank);

这行代码用于输出当前元素 i 的状态信息。具体来说：
%d 是格式说明符，用于输出整型数据。
i 表示当前元素的索引。
parentArray[i].parent 表示当前元素的父节点。
parentArray[i].rank 表示当前元素所在树的高度（秩）。
\t 用于在各个数据项之间插入制表符，使输出内容对齐，便于阅读。
\n 在每次输出完一个元素的状态后换行，以便下一个元素的状态输出在新的一行。

6.主函数逻辑

变量声明与初始化：

int choice, n, x, y;

声明了几个整型变量，用于存储用户的选择、元素数量以及用户输入的元素索引。

printf("请输入元素的数量：");

提示用户输入元素的数量。

scanf_s("%d", &n);

读取用户输入的整数并存储到变量n中。

initialize(n);调用初始化函数，根据用户输入的元素数量初始化并查集。

主循环与菜单显示：

while (1)

创建了一个无限循环，用于持续显示菜单并处理用户的选择，直到用户选择退出。

printf("\n并查集操作界面\n");

等语句打印操作界面的菜单选项，包括合并两个集合、查找元素所在集合的根节点、显示当前并查集状态和退出程序。

用户选择处理：scanf_s("%d", &choice);读取用户输入的操作选择。switch (choice)根据用户的选择执行不同的操作：
合并操作（case 1）：提示用户输入两个要合并的元素的索引，检查输入是否在有效范围内，如果有效则调用unionSets(x, y)进行合并，并输出合并结果；如果无效则提示输入超出范围。

查找操作（case 2）：提示用户输入要查找的元素的索引，检查输入是否有效，如果有效则调用find(x)查找该元素所在集合的根节点并输出结果；如果无效则提示输入超出范围。

显示操作（case 3）：调用display()函数显示当前并查集的状态，包括每个元素的索引、父节点和秩。

退出操作（case 4）：输出退出提示，释放为parentArray分配的内存（防止内存泄漏），然后调用exit(0)函数退出程序。

默认情况（default）：如果用户输入的选择

7.整个并查集代码的流程大致如下：

用户输入元素数量 ：在 main 函数中，首先提示用户输入元素的数量 n。
初始化并查集 ：调用 initialize 函数，根据用户输入的元素数量 n，为 parentArray 动态分配内存，并将每个元素的父节点初始化为自身（parent = i），秩初始化为 1（rank = 1）。同时将 size 变量置为 n。
用户选择操作 ：通过一个循环显示操作菜单，让用户选择进行合并操作、查找操作、显示当前状态或退出程序。
合并操作 ：当用户选择合并两个集合时，输入两个元素的编号，调用 unionSets 函数。该函数首先分别查找这两个元素所在集合的根节点，如果根节点不同，则根据按秩合并的原则将一个树合并到另一个树上。
查找操作 ：当用户选择查找元素所在集合的根节点时，输入一个元素的编号，调用 find 函数。该函数利用路径压缩的优化策略查找根节点，并在查找过程中将沿途节点的父节点直接指向根节点，以加速后续查找。
显示状态操作 ：当用户选择显示当前并查集状态时，调用 display 函数，遍历 parentArray，输出每个元素的编号、父节点和秩。
退出程序 ：用户选择退出时，释放为 parentArray 分配的内存，并退出程序。

 

三、完整代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// 并查集元素结构体，记录父节点和秩（树的高度）
typedef struct 
{    
    int parent;    
    int rank;
} DisjointSet;

DisjointSet* parentArray;
int size = 0;

// 初始化并查集
void initialize(int n) 
{    
    parentArray = (DisjointSet*)malloc(n * sizeof(DisjointSet));    
    if (parentArray == NULL)           // 检查内存分配是否成功    
    {          
        printf("内存分配失败！\n"); 
        exit(EXIT_FAILURE); // 分配失败，终止程序    
    } 
   
    for (int i = 0; i < n; i++)    
    {        
        parentArray[i].parent = i;        
        parentArray[i].rank = 1;    
    }    
    size = n;
}

// 查找根节点，并进行路径压缩
int find(int x) 
{    
    if (parentArray[x].parent != x) 
    {        
         parentArray[x].parent = find(parentArray[x].parent);
    }   
     return parentArray[x].parent;}

// 按秩合并
void unionSets(int x, int y) 
{    
    int xRoot = find(x);   
    int yRoot = find(y);    
    if (xRoot == yRoot) 
    {        
        return;
    }    
    if (parentArray[xRoot].rank < parentArray[yRoot].rank) 
    {        
        parentArray[xRoot].parent = yRoot;
    }    
    else if 
    (
        parentArray[xRoot].rank > parentArray[yRoot].rank) 
    {        
        parentArray[yRoot].parent = xRoot;
    }    
    else 
    {        
        parentArray[yRoot].parent = xRoot;
        parentArray[xRoot].rank++;    
    }    
}

// 显示当前并查集的连接状态
void display() 
{    
    printf("\n元素\t父节点\t秩\n");
    for (int i = 0; i < size; i++) 
    {        
        printf("%d\t%d\t%d\n", i, parentArray[i].parent, parentArray[i].rank);
    }
}


int main() 
{    
    int choice, n, x, y;
    printf("请输入元素的数量：");
    scanf_s("%d", &n);
    initialize(n);
    while (1) 
    {        
        printf("\n并查集操作界面\n");
        printf("1. 合并两个集合\n");
        printf("2. 查找元素所在集合的根节点\n");
        printf("3. 显示当前并查集状态\n");
        printf("4. 退出\n");
        printf("请输入您的选择：");
        scanf_s("%d", &choice);
        switch (choice)
        {        
        case 1:
            printf("请输入两个要合并的元素（0 - %d）：", n - 1);
            scanf_s("%d %d", &x, &y); 
            if (x >= 0 && x < n && y >= 0 && y < n) 
            {                
                unionSets(x, y);
                printf("元素 %d 和 %d 已合并\n", x, y);
            }            
            else 
            {                
                printf("输入的元素超出范围！\n");
            }            
            break;  
      
        case 2:
            printf("请输入要查找的元素（0 - %d）：", n - 1);
            scanf_s("%d", &x);
            if (x >= 0 && x < n) 
            {                
            printf("元素 %d 所在集合的根节点是：%d\n", x, find(x));
            }
            else 
            {                
            printf("输入的元素超出范围！\n");
            }            
            break;
        
        case 3:            
            display();
            break;

        case 4: 
            printf("退出程序\n");
            free(parentArray);
            exit(0);

        default:           
            printf("无效的选择，请重新输入！\n");
       }    
    }    
return 0;
}