代码随想录算法训练营Day47 | 并查集理论基础、107.寻找存在的路线

并查集理论基础

一、核心思想

高效处理动态连通性问题。

并查集用于判断两个元素是否在同一个集合中。它将每个集合看作一棵树，集合的“代表”就是这棵树的根节点。如果两个元素的根节点相同，它们就在同一个集合。

二、三大核心操作

1. 初始化
   • 功能：开始时，每个元素都是一个独立的集合，其根节点是自己。
   • 代码：

void init(int n) { for (int i = 0; i < n; ++i) { father[i] = i; // 每个节点的父节点都是自己 } }

1. 寻根
   • 功能：找到指定元素所在集合的根节点。这是并查集的灵魂。
   • 优化（路径压缩）：在寻找根的过程中，将路径上的所有节点直接指向根节点，极大提升后续查询效率。
   • 代码：

int find(int u) { // 如果u的父节点不是自己，就递归寻找，并把u的父节点直接设置为根 return u == father[u] ? u : father[u] = find(father[u]); }

1. 合并
   • 功能：将两个元素所在的集合合并成一个。
   • 核心原则：必须先找到两个元素的根节点，再将其中一个根节点连接到另一个上。
   • 代码：

void join(int u, int v) { u = find(u); // 找到u的根 v = find(v); // 找到v的根 if (u == v) return; // 如果根相同，说明已在同一集合，无需操作 father[v] = u; // 将v的根连接到u的根上 }

1. 判断
   • 功能：判断两个元素是否在同一个集合。
   • 代码：

bool isSame(int u, int v) { return find(u) == find(v); }

三、常见误区：join函数的正确写法

错误写法：

void join(int u, int v) { if (isSame(u, v)) return; // 虽然判断对了，但... father[v] = u; // ...这里连接的是原始节点u和v，而不是它们的根！ }

• 问题：这样会破坏树的结构，导致后续find操作出错。例如，join(1, 2); join(3, 2);后，isSame(1, 3)会返回false，不符合预期。

正确写法：

void join(int u, int v) { u = find(u); // 必须先找根！ v = find(v); // 必须先找根！ if (u == v) return; father[v] = u; // 连接的是根节点 }

• 原因：保证了总是将两个集合的根进行连接，维护了数据结构的正确性。

四、另一个优化：按秩合并

• 思想：在合并时，总是将“秩”（可以理解为树的高度或大小）较小的树挂载到较大的树上，避免树的高度过快增长。
• 虽然理论上很好，但路径压缩的优化效果已经非常出色，且代码更简洁。在实际应用和面试中，通常只使用路径压缩就足够了。

五、完整代码模板

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩 } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } // 将v->u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; }

六、复杂度分析

• 空间复杂度：O(n)，需要一个father数组。
• 时间复杂度：接近 O(1)。
  • 路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
  • 路径压缩保证了每次操作后，树的结构都趋向于扁平化，使得后续的查询和合并操作非常快。

KamaCoder107.寻找存在的路线

107. 寻找存在的路线

1.思路

本题是并查集的模板题，掌握基础模板就能直接拿下。

#include <iostream> #include <vector> using namespace std; int n,m; vector<int>father(105,1); void init(){ for(int i=1;i<=n;i++){ father[i]=i; } } int find(int u){ if(u==father[u]) return u; return father[u]=find(father[u]); } bool issame(int u,int v){ u=find(u); v=find(v); return u==v; } void join(int u,int v){ u=find(u); v=find(v); if(u==v) return; father[u]=v; } int main(){ cin>>n>>m; init(); for(int i=0;i<m;i++){ int s,t;cin>>s>>t; join(s,t); } int source,destination; cin>>source>>destination; cout<<issame(source,destination); return 0; }

2.Reference：107. 寻找存在的路径 | 代码随想录