Day60_补20250208_图论part5_并查集理论基础|寻找存在的路径
Day60_20250208_图论part5_并查集理论基础|寻找存在的路径
并查集理论基础
- 明确并查集解决什么问题，代码如何写
并查集
-
作用：解决连通性问题。【当我们需要判断2个元素是否在同一个集合里的时候，要想到使用并查集】
-
功能
- 将2个元素添加到1个集合中
- 判断2个元素在不在同一个结合
-
原理
- 将3个元素放在同一个集合里
-
A，B，C连通，一维数组，father[A]=B;father[B]=C,因此A和B和C连通了(有向连通图)
-
核心：寻根思路，只要A，B，C在同一个根下就是同一个集合。
-
寻根主代码
//将u,v这条边加入并查集 void join(int u,int v){ u=find(u);//寻找u的根 v=find(v);//寻找v的根 if(u==v) return;//如果发现根相同，说明在一个集合，不用2个节点相连直接返回 father[v]=u; }
-
-
寻根 find()
-
代码
int find(int u){ if(u==father[u]) return u;//如果根就是自己，直接返回 else return find(father[u]);//如果根不是自己，就根据数组下标一层一层向下找 }
-
-
初始化，默认自己指向自己 father[i]=i; （如何表示C也在同一个元素里）
-
代码
//并查集初始化 void init(){ for(int i=0;i<n;i++){ father[i]=i; } }
-
-
判断2个元素是否在同一个集合里，同根则在同集合
-
代码
//判断u和v是否找到同一个根 bool isSame(int u,int v){ u=find(u); v=find(v); return u==v; }
-
-
路径压缩：除了根节点其他所有节点都挂载根节点下，寻根很快只需要1步
-
将非节点的所有节点直接指向根节点。
-
【靠压缩路径来缩短查询根节点的时间】
-
代码1
//并查集里寻根的过程 int find(int u){ //如果自己是根节点 if(u==father[u]) return u; //否则，路径压缩，将当前的节点指向根节点 else return father[u]=find(father[u]);//路径压缩 } -
代码2 三元运算符
int find(int u){ return u=father[u]?u:father[u]=find(father[u]); }
-
-
代码模板
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 // 并查集初始化 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; }
-
- 将3个元素放在同一个集合里
-
并查集的三个功能
- 寻找根节点，find(int u); 判断这个节点的祖先节点是哪个
- 将两个节点接入到同一个集合，join(int u,int v);将两个节点连在同一个根节点上
- 判断两个节点是否在同一个集合，isSame(int u,int v) 判断两个节点是不是同一个根节点
-
注意事项
- join(int u,int v) join函数分别对u和v寻根之后再进行关联。
-
除路径压缩方法外：按秩(rank)合并，rank表示树的高度，即树中结点层次的最大值。
-
两个集合(多叉树)需要合并
- 树2合并到树1还是树1合并到树2？
- rank小的树合入到rank大的树，保证最后合成的树rank最小，降低在树上查询的路径长度
-
代码
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; rank[i] = 1; // 也可以不写 } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? 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 (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树 else father[v] = u; if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <= } -
路径压缩:无论使用并查集模板里哪一个函数(init函数)，都会有路径压缩的过程。第二次访问该结点时，这个结点是直连根结点的，即第一次访问的时候它的路径就被压缩了。
-
-
复杂度
- 空间复杂度，O(n)，申请一个father数组
- 时间复杂度，
- 路径压缩后的并查集时间复杂度在O(logn)于O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
- 在第一次查询的时候，相当于是n叉树上从叶子节点到根节点的查询过程，logn，但路径压缩后，后面的查询操作都是O(1)，而join函数和isSame函数里涉及的查询操作是一样的过程。
寻找存在的路径
题目
题目描述
给定一个包含 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。
思路
-
思路(并查集)
- 并查集问题：2个节点在不在1个集合；将2个节点添加到1个集合中
- 核心：判断1个顶点到另一个顶点有没有有效路径就是看这两个顶点是否在同一个集合里。如何算是同一个集合呢，有边连在一起就算是一个集合。
- 使用join(int u,int v)将每条边加入到并查集，最后用isSame(int u,int v)判断是否是同一个根就可以了。
-
模板
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 // 并查集初始化 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; } -
代码
import java.util.*; public class Main{ public static void main(String[] args){ //输入 int N,M; Scanner scanner=new Scanner(System.in); N=scanner.nextInt(); M=scanner.nextInt(); DisJoint disJoint =new DisJoint(N+1);//实例化对象 //N和M分别代表节点的个数、边的个数 //构建图论，将2个节点接入到同一集合中 for(int i=0;i<M;i++){ disJoint.join(scanner.nextInt(),scanner.nextInt()); } //判断两个顶点是否存在于同一集合中 if(disJoint.isSame(scanner.nextInt(),scanner.nextInt())){ System.out.println("1"); }else{ System.out.println("0"); } } } //并查集模板 //初始化 init() //寻找根节点 find() //将2个节点接入到同一个集合中 join() //判断2个节点是否在同一个集合 isSame class DisJoint{ private int[] father;//父节点 //初始化 默认自己指向自己 public DisJoint(int N){ father=new int[N]; for(int i=0;i<N;i++){ father[i]=i; } } //寻找根节点 public int find(int n){ return n==father[n]?n:(father[n]=find(father[n])]; } //根据根节点将2个节点接入到同一个集合中 public void join(int n,int m){ n=find(n); m=find(m); if(n==m) return; father[m]=n; } //判断2个集合是否在同一个集合中 public boolean isSame(int n,int m){ n=find(n); m=find(m); return n==m; } }
总结
- 熟记并查集模板