严文韬的博客

并查集 – Kruskal

题意：n个朋友，，m对互相认识，认识的坐一桌，问需要几张桌子

分析：就是求有几个集合，根节点数就是集合数。有kruskal算法即可。

AC代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define MAXN 1005int p[MAXN];int Find(int x){return x==p[x]?x:(p[x]=Find(p[x]));}void Union(int R1, int R2){int r1 = Find(R1);int r2 = Find(R2);if(r1 != r2) p[r1] = r2;else {}}int main(){int n, m;int t, i, u, v, cnt;scanf("%d",&t);while(t–){cnt = 0;scanf("%d%d",&n, &m);for(i=1; i<=n; i++){p[i] = i;}for(i=1; i<=m; i++){scanf("%d%d",&u, &v);Union(u, v);}for(i=1; i<=n; i++){if(p[i] == i)cnt++;}printf("%d\n", cnt);//getchar();}return 0;}

效果只能是既费时又没有胜利，再聪慧的人也没法成学。