并查集理论基础
并查集的本质是一种维护不相交集合的数据结构。其核心思想是用树形结构来表示集合，每个集合是一棵树。
基本概念
- 并查集维护了一个由不同元素构成的不相交集合
- 每个集合用一棵树来表示，树的根节点是该集合的代表元素
- 同一棵树中的所有节点属于同一个集合
核心操作 Find操作:
- 功能：查找元素所在集合的代表元素（根节点）
- 实现：从当前节点不断往上查找父节点，直到找到根节点
Union操作:
- 功能：合并两个集合
- 实现：将一个集合的根节点指向另一个集合的根节点
优化策略
1.路径压缩（Path Compression）:
- 在执行find操作时，将搜索路径上的所有节点直接连接到根节点
- 显著减少树的高度，提高后续操作效率
按秩合并（Union by Rank）:
- 记录每棵树的高度（秩）
- 总是将较矮的树挂在较高的树下面
- 可以保证树的高度不会无限增长
代码模板：
#include <stdio.h>#define N 10001 // 根据实际问题调整大小int p[N]; // 父节点数组
int rank[N]; // 秩数组，用于按秩合并// 初始化
void init(int n) {for(int i = 0; i < n; i++) {p[i] = i; // 每个节点的父节点初始化为自己rank[i] = 1; // 初始的秩都为1}
}// 查找根节点（路径压缩）
int find(int x) {if(p[x] != x) p[x] = find(p[x]);return p[x];
}// 合并（按秩合并）
void unite(int x, int y) {x = find(x);y = find(y);if(x == y) return;if(rank[x] < rank[y]) {p[x] = y;} else {p[y] = x;if(rank[x] == rank[y]) rank[x]++;}
}// 判断是否连通
int same(int x, int y) {return find(x) == find(y);
}// 使用示例
int main() {int n = 10; // 假设有10个节点init(n);// 合并一些集合unite(1, 2);unite(2, 3);unite(4, 5);// 判断连通性printf("%d\n", same(1, 3)); // 输出1，表示1和3连通printf("%d\n", same(1, 4)); // 输出0，表示1和4不连通return 0;
}
107.寻找存在的路径
题目描述
给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
输入描述
第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
输出描述
输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。
输入示例
5 4
1 2
1 3
2 4
3 4
1 4
输出示例
1
提示信息
数据范围：
1 <= M, N <= 100。
思路：
这道题直接用上面的思想就能解决，没有什么过多的思路，但是对于并查集还是要认真学习。
解答：
#include <stdio.h>
#include <stdbool.h>
#define NUM 1000
int P[NUM];
void init(int n)
{for(int i = 0;i < n;i++){P[i] = i;}
}
int find(int x)
{if(P[x] != x)P[x] = find(P[x]);return P[x];
}
bool issame(int x,int y)
{return find(x) == find(y);
}
void unite(int x, int y) {P[find(x)] = find(y);
}
int main()
{int N,M;scanf("%d %d",&N,&M);init(N);for(int i = 0;i < M;i++){int s,t;scanf("%d %d",&s,&t);unite(s,t);}int source,destination;scanf("%d %d",&source,&destination);if(issame(source,destination)){printf("1");}else{printf("0"); }
}
