并查集及其应用

题目后续补吧,主要解决问题;

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5;
 4 int fa[N]; 
 5 int find_fa(int x){
 6     return fa[x]=(x==fa[x])?x:find_fa(fa[x]);//路径压缩
 7 }
 8 void merge(int x,int y)
 9 {
10     int fx=find_fa(x),fy=find_fa(y);//这里是随机合并,也可以用按秩合并;
11     fa[fy]=fx;
12 } 
13 int main()
14 {
15     //1.处理无向图的连通分量
16     //2.处理最小生成树,边从小到大选n-1条边,如果一条边的两个点不在同一集合就加边 
17     //证明,最小的n-1条边能型形成n个点的数,如果存在一条小边成环,则去说明去到较大的留下更小的会从u->v更优; 
18     return 0;
19 }

 

上一篇:前端鄙视题


下一篇:python写出1A2B游戏