【算法分析】
Kruskal 算法的贪心思想体现在“始终优先选权值最小且不构成环的边”。
并查集在 Kruskal 算法中，核心作用就是快速判断当前边是否会构成环。
【算法代码一：基础版】
特别注意：利用并查集处理问题时，千万不要忘了初始化操作 pre[i]=i。
#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
int pre[N];int find(int x) {if(x!=pre[x]) pre[x]=find(pre[x]);return pre[x];
}void merge(int x,int y) {int a=find(x);int b=find(y);if(a!=b) pre[a]=b;
}int main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) pre[i]=i;bool flag=false;while(m--) {int u,v;cin>>u>>v;int fu=find(u);int fv=find(v);if(fu==fv) flag=true;else merge(u,v);}if(flag) cout<<"has circle"<<endl;else cout<<"no circle"<<endl;return 0;
}/*
in:
3 3
1 2
2 3
1 3out:
has circle
-----------
in:
4 3
1 2
2 3
3 4out:
no circle
*/
【算法代码二：优化版（按秩合并 + 路径压缩，大数据更稳）】
#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
int pre[N],rnk[N];int find(int x) {if(x!=pre[x]) pre[x]=find(pre[x]);return pre[x];
}void merge(int x,int y) { //合并两个子集int a=find(x);int b=find(y);if(rnk[a]<=rnk[b]) pre[a]=b;else pre[b]=a;if(rnk[a]==rnk[b] && a!=b) rnk[b]++;
}//如果深度相同且根结点不同，则新的根结点的深度+1int main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) {pre[i]=i;rnk[i]=1;}bool flag=false;while(m--) {int u,v;cin>>u>>v;int fu=find(u);int fv=find(v);if(fu==fv) flag=true;else merge(u,v);}if(flag) cout<<"has circle"<<endl;else cout<<"no circle"<<endl;return 0;
}/*
in:
3 3
1 2
2 3
1 3out:
has circle
-----------
in:
4 3
1 2
2 3
3 4out:
no circle
*/
【参考文献】