本文主要是介绍kruskal_并查集_代码模板 hdu1232，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
kruskal代码模板
input
a _the number of verteices
b _the number of edges
v1_verteices
wi_the weight of each edge
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctype.h>
#include<algorithm>
#include<map>
#include<vector>
#include<set>#define MAX 100005
#define MOD 1000003
#define inf 100000000
#define eps 1e-9
#define pi acos(-1.0)
#define LL long long
#define I64 __int64
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))using namespace std;struct edge {int v1, v2, w;
};int edge_num, vertex_num;
edge volume_e[30];
int father[30];int cmp (edge a, edge b) {return a.w < b.w;
}int find (int x) {int root = x;for (father[root] != root)root = father[root];return root;
}int main()
{freopen ("in.txt", "r", stdin);cin >> edge_num >> vertex_num;// the number of edge and vertex// v1, v2, weightfor (int i = 0;i < edge_num;i ++)scanf ("%d %d %d", &volume_e[i].v1, &volume_e[i].v2, &volume_e[i].w);// initialfor (int i = 1;i <= vertex_num;i ++) father[i] = i;sort (volume_e, volume_e+edge_num, cmp);int sum = 0;for (int i = 0; i < edge_num;i ++){int x = find (volume_e[i].v1);int y = find (volume_e[i].v2);if (x != y){sum += volume_e[i].w;father[x] = y;}}printf ("%d\n", sum);
}/*
5 5
1 2 2
2 3 3
1 4 1
3 4 2
4 5 4*/HDU1232
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctype.h>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
using namespace std;int add;
int f[100010];
int n, m;int findset(int x)
{int set = x;while(f[set] != set){set = f[set];}return set;
}void merge(int a, int b)
{int x = findset(a);int y = findset(b);if(x != y)f[x] = y;
}int main()
{freopen("in.txt", "r", stdin);while(scanf("%d %d", &n, &m) == 2){add = 0;if(n == 0)break;else if(m == 0){add = n - 1;printf("%d\n", add);}else{for(int i = 1; i <= n; i++) f[i] = i;for(int i = 0; i < m; i++){int a, b;scanf("%d %d", &a, &b);merge(a, b);}for(int i = 1; i <= n; i++)if(f[i] == i)add++;add--;printf("%d\n", add);}//memset(f, 0, sizeof(f));}
}/*
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0*/这篇关于kruskal_并查集_代码模板 hdu1232的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
