共计 5103 个字符，预计需要花费 13 分钟才能阅读完成。
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 = 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;
}
