bingchaji_kruskal.rar_并查集

#include <cstdlib> #include <iostream> using namespace std; #define MAXN 1000 #define NUM 1000*1000 #define inf 1<<30 //31 is overflowing int P[MAXN]; int rank[MAXN]; void Make_set(int x) { P[x] = x; rank[x] = 0; //合并两集合的一个启发函数值 } int Find_set(int x) { if(x != P[x]) P[x] = Find_set(P[x]); return P[x]; } void Link_set(int x,int y) { if(rank[x] > rank[y]) P[y] = x; else P[x] = y; if(rank[x] == rank[y]) rank[y]++; } void Union_set(int x,int y) { Link_set(Find_set(x),Find_set(y)); } /////基于并查集的求最小生成树的Kruskal算法的实现 ////if (u,v) is not exist,G[u][v] = inf ////if u has been added in set of the smallest tree,then G[u][u] = 1; int e[MAXN][MAXN]; struct Tree{ int u; int v; int value; }; Tree tree[NUM]; int count_n = 0; void st_Kruskal(int n) { int i = 0,j = 0; for(i = 0;i < n;i++) { Make_set(i); } int u = 0,v = 0; count_n = 0; while(1) { int min = inf; for(i = 0;i < n;i++) { for(j = 0;j < n;j++) { if(i != j && e[i][j] < min) { min = e[i][j]; u = i,v = j; } } } if(min == inf) break; if(Find_set(u) != Find_set(v)) { tree[count_n].u = u; tree[count_n].v = v; tree[count_n].value = e[u][v]; Union_set(u,v); e[u][u] = e[v][v] = 1; count_n++; } e[u][v] = inf; } } int main() { int n = 0,i = 0,j = 0; while(cin>>n) { for(i = 0;i < n;i++) { for(j = 0;j < n;j++) { cin>>e[i][j]; if(e[i][j] == -1) e[i][j] = inf; } } st_Kruskal(n); for(i = 0;i < count_n;i++) { cout<<tree[i].u<<" "<<tree[i].v<<" "<<tree[i].value<<endl; } } return 0; } test: 6 0 6 2 -1 -1 -1 6 0 1 11 -1 -1 2 1 0 9 13 -1 -1 11 9 0 3 4 -1 -1 13 3 0 4 -1 -1 -1 4 4 0 result: 1 2 1 0 2 2 3 4 3 3 5 4 2 3 9