并查集:找祖先并更新,注意路径压缩,不然会时间复杂度巨大导致出错/超时
合并:(我的祖先是的你的祖先的父亲)
找父亲:(初始化祖先是自己的,自己就是祖先)
查询:(我们是不是同一祖先)
路径压缩:(每个点只保存祖先,不保存父亲)
最小生成树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; }