How Many Tables（并查集）
Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
Input
The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.
Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
Sample Input
2
5 3
1 2
2 3
4 5
5 1
2 5
Sample Output
2
4
//(并查集)#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<cstdio>#include<queue>#include<stack> #include<set> #include<vector> using namespace std;const int maxn = 1005;int s[maxn];//并查集数组 int Find(int x){//寻找某结点所在的汇合 if(x == s[x]){ return x; }else{ s[x] = Find(s[x]);//一直往上递归查找father并进行门路压缩 return s[x]; }}void unionn(int i,int j){//合并i,j所在的汇合 int i_f = Find(i); int j_f = Find(j); if(i_f != j_f){ s[i_f] = j_f;//i的先人（代表元素或所在汇合)为j } }int main(){ int t = 0; cin >> t; while(t--){ int n = 0,m = 0; cin >> n >> m; for(int i = 1; i <= maxn; i++){ s[i] = i;//各数初始汇合为本身 } int x,y;//输出两个意识的敌人组 for(int j = 1; j <= m; j++){ cin >> x >> y; unionn(x,y);//合并两个敌人所在的汇合 } int ans; ans = 0; for(int k = 1; k <= n; k++){ if(k == s[k]){ ans++; } } cout << ans << endl; } return 0;} 还是畅通工程（最小生成树）
某省考察农村交通状况，失去的统计表中列出了任意两村庄间的间隔。省政府“畅通工程”的指标是使全省任何两个村庄间都能够实现公路交通（但不肯定有间接的公路相连，只有能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输出蕴含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的间隔，每行给出一对正整数，别离是两个村庄的编号，以及此两村庄间的间隔。为简略起见，村庄从1到N编号。
当N为0时，输出完结，该用例不被解决。
Output
对每个测试用例，在1行里输入最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
Huge input, scanf is recommended.
本题别离采纳prime和kruskal来解决最小生成树问题，尽量以kruskal为主
//prime算法求最小生成树#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<cstdio>#include<queue>#include<stack> #include<set> #include<vector> using namespace std;const int INF = 0x3f3f3f3f;//x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级//而个别场合下的数据都是小于10^9的。0x3f3f3f3f * 2 = 2122219134，无穷大相加仍然不会溢出。 int m,n;//m示意要图要输出的门路数,n示意村庄数int x,y,z;//x,y,z别离代表两个村庄和间隔int dis[10005],vis[105];//dis[] 示意两个村庄的间隔(dis[i]即可示意与i点相连的所有边的长度)，vis[]标记是否被已选为过点 int mp[100][100];//为任意两个村庄的间隔赋初值用void prime(){ dis[1] = 0;//开始为0，只有一个点没有间隔,前面要逐一点进行for循环，也须要将第一个点退出 已有点 的汇合 int k = 1;//先把1退出标记已拜访 while(1){// int k = 1;//用k是否变动来标记是否曾经找到 已有点 到其余各点的最短门路，找到就把那个点赋值给k int count = 0; int minnum = INF;//每次循环minnum值都从新变为INF // for(int j = 1; j <= n; j++){// if(mp[k][j] < dis[j]&& vis[j] == 0){//比拟所有与k相连的点的间隔找某点到其余点的最短门路 // dis[j] = mp[k][j];//把最小的值赋给dis[j] // }// } // for(int i = 1; i <= n; i++){//找 已有点 相连边集中的最小边 // if(dis[i] < minnum && vis[i] == 0){//如果找到比minnum值小的dis[i]值(找与已有点汇合的点相连的最小边的点)，就替换原来minnum的值 // minnum = dis[i];//每次while循环minnum值都从新变为INF // k = i;//示意找到一点k退出 已有点 汇合 // }// }// if(k == -1){//k值没变，曾经遍历完，所有下面for()找中vis[]都不是0 // break; // } vis[k] = 1;//退出汇合后标记 for(int j = 1; j <= n; j++){//起到两个作用：找到任何点与j相连的最短门路dis[1],[2],[3],[4].....并mp[1][1],[2][1],[3][1]等等不断更新最小的dis[1] if(mp[k][j] < dis[j]&& vis[j] == 0){//比拟所有与k相连的点的间隔找某点到其余点的最短门路 dis[j] = mp[k][j];//把最小的值赋给dis[j] } } for(int i = 1; i <= n; i++){//找 已有点 相连边集中的最小边(各dis中的最小值) if(dis[i] < minnum && vis[i] == 0){//如果找到比minnum值小的dis[i]值(找与已有点汇合的点相连的最小边的点)，就替换原来minnum的值 minnum = dis[i];//每次while循环minnum值都从新变为INF k = i;//示意找到一点k退出 已有点 汇合 count++; } } if(count == 0){//count值没变，曾经遍历完，所有下面for()找中vis[]都不是0 break; } } int ans = 0; for(int i = 1; i <= n; i++){ ans += dis[i];//将所有最短门路加起来 } cout << ans << endl; } int main(){ while(scanf("%d",&n)!=EOF,n != 0){ m = n * (n - 1)/2; memset(vis,0,sizeof(vis));//初始化标记数组为0 memset(dis,INF,sizeof(dis));//初始化标记数组为无穷大 for(int i = 1; i <= n; i++){//初始化一下mp临接矩阵 for(int j = 1; j <= n; j++){ if(i == j){//点自身到自身的间隔为0 mp[i][j] = 0; }else{//其余点到点间隔初始化为无穷大 mp[i][j] = mp[j][i] = INF; } } } for(int i = 0; i < m; i++){ cin >> x >> y >> z;//给相互之间有门路的点赋值，其余未联通的点之间值仍是无穷大 if(mp[x][y] > z){//防止出现给出两组村庄雷同然而间隔不同的测试数据 mp[x][y] = z;//确保间隔是最小的 mp[y][x] = z;//邻接矩阵两边都要赋值 } } prime(); } return 0;} 上面是克鲁斯卡尔算法联合并查集来求最小生成树
//(kruskal算法(并查集)求最小生成树) #include<iostream>#include<algorithm>#include<string>#include<string.h>#include<cstdio>#include<queue>#include<stack> #include<set> #include<vector> using namespace std;//const int INF = 0x3f3f3f3f;//x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级//而个别场合下的数据都是小于10^9的。0x3f3f3f3f * 2 = 2122219134，无穷大相加仍然不会溢出。const int maxn = 105;struct Edge{ int u,v,w;//别离代表构造体变量的 村庄1，村庄2，间隔 }edge[maxn*maxn];//定义一个邻接表构造体数组 bool cmp(Edge a,Edge b){ return a.w < b.w;} int m,n,s[maxn];//m示意要图要输出的门路数,n示意村庄数,s[maxn]代表数组汇合并查集用到 int Find(int x){ if(x == s[x]){ return x; }else{ s[x] = Find(s[x]);//一直往上递归查找father并进行门路压缩 return s[x]; }} int Kruskal(){ int ans ; ans = 0; for(int i = 1; i <= n; i++){//初始化，所在汇合开始为其本身 s[i] = i; } sort(edge,edge + m,cmp); for(int i = 0; i < m; i++){ int b = Find(edge[i].u); int c = Find(edge[i].v); if(b == c){//示意edge[i]的两个顶点曾经同在一个汇合中，不必在并入（此处也可防止树成环） continue; } s[b] = c;// s[c] = b; ans += edge[i].w; } return ans; } int main(){ while(scanf("%d",&n)!=EOF,n){ m = n * (n - 1)/2; for(int i = 0; i < m; i++){ scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); } int ans; ans = 0; ans = Kruskal(); printf("%d\n",ans); } return 0;}