并查集: 找祖先并更新, 注意路径压缩, 不然会时间复杂度巨大导致出错 / 超时
合并:(我的祖先是的你的祖先的父亲)
找父亲:(初始化祖先是自己的, 自己就是祖先)
查询:(我们是不是同一祖先)
路径压缩:(每个点只保存祖先, 不保存父亲)
最小生成树 kruskal: 贪心算法 + 并查集数据结构, 根据边的多少决定时间复杂度, 适合于稀疏图
核心思想贪心, 找到最小权值的边, 判断此边连接的两个顶点是否已连接, 若没连接则连接, 总权值 += 此边权值, 已连接就舍弃继续向下寻找;
并查集数据结构程序:
- #include<iostream>
- #define re register
- using namespace std;
- int f[10010],n,m,x,y,z;
- int father(int k)
- {
- if(f[k]==k)
- return k;
- else
- return f[k]=father(f[k]);
- }
- void close(int a,int b)
- {
- int fa,fb;
- fa=father(a);
- fb=father(b);
- f[fa]=fb;
- }
- void find(int a,int b)
- {
- if(father(a)==father(b))
- cout<<'Y'<<endl;
- else
- cout<<'N'<<endl;
- }
- int main()
- {
- cin>>n>>m;
- for(re int i=1;i<=n;i++)
- f[i]=i;
- for(re int i=1;i<=m;i++)
- {
- cin>>x>>y>>z;
- if(x==1)
- close(y,z);
- else
- find(y,z);
- }
- return 0;
- }
最小生成树 kruskal 算法程序
- #include <iostream>
- #include <stdio.h>
- #include <algorithm>
- using namespace std;
- int f[5002],ans=0,s=0;
- struct node
- {
- int x;
- int y;
- int data;
- }c[200002];
- bool cmp(node a,node b)
- {
- return a.data<b.data ;
- }
- int father(int k)
- {
- if(f[k]==k)return k;
- else
- return f[k]=father(f[k]);
- }
- bool find(int a,int b)
- {
- if(father(a)==father(b))
- return true;
- else
- return false;
- }
- void merge(int a,int b)
- {
- int fa,fb;
- fa=father(a);
- fb=father(b);
- f[fa]=fb;
- }
- int main()
- {
- int n,m;
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- {
- f[i]=i;
- }
- for(int i=1;i<=m;i++)
- {
- cin>>c[i].x>>c[i].y>>c[i].data ;
- }
- sort(c+1,c+m+1,cmp);
- for(int i=1;i<=m;i++)
- {
- if(!find(c[i].x,c[i].y))
- {
- merge(c[i].x,c[i].y);
- ans+=c[i].data;
- s++;
- }
- if(s==n-1)break;
- }
- if(s==n-1)
- cout<<ans;
- }
来源: http://www.bubuko.com/infodetail-2604660.html