题目后续补吧,主要解决问题;
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 }