现在有10个强盗，下面9行两个人是一个团伙 1 2 3 4 5 2 4 6 2 6 8 7 9 7 1 6 2 4 求有几个团伙
//并查集 #include<stdio.h> int f[1000]={0},n,m,k,sum=0; //第一步，这里是初始，非常的重要，数组里面存自己的下标就好了（自己是自己的老大） void init() { int i; for(i=1;i<=n;i++) f[i]=i; return ; } //这是找爹的递规函数，不停的去找爹，直到找到祖宗为止，其实就是去犯罪团伙的最高领导，“擒贼先擒王”原则 int getf(int v) { if(f[v]==v) return v; else { f[v]=getf(f[v]);//找爹循环，哈哈哈 return f[v];//返回找到的值 } } //这里是合并两子集合的函数 void merge(int v,int u) { int t1,t2; t1=getf(v);//注意这里是getf(v),不是getf(f[v]),要不然就隔过了一层找爹循环 t2=getf(u); if(t1!=t2)//判断两节点是否同一祖先 { //靠左原则 f[t2]=t1; } return ; } int main() { int i,x,y; scanf("%d%d",&n,&m); //初始化为第一步 init(); //第二步合并团伙，题型可能有改动，但是万变不离其宗 for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); merge(x,y); } //第三步扫描有多少团伙 for(i=1;i<=n;i++) { if(f[i]==i) sum++; } printf("%d\n",sum); getchar();getchar(); return 0; } //答案为3有好几个孤岛，要把它们连起来，且花费最少 数据 6 9 2 4 11 3 5 13 4 6 3 5 6 4 2 3 6 4 5 7 1 2 1 3 4 9 1 3 2 找到n-1条边，使得n个岛连通且路程最短
//最小生成树kruskal算法 //核心：排序，选用n-1条边 #include <stdio.h> #include<iostream> #include<algorithm> using namespace std; struct edge { int u,v,w; }e[10]; int cmp(edge x,edge y) { return x.w<y.w; } int n,m; int f[7]={0},sum=0,cou=0; int geft(int v) { if(f[v]==v) return v; else { f[v]=geft(f[v]); return f[v]; } } int merge(int v,int u) { int t1,t2; t1=geft(v); t2=geft(u); if(t1!=t2) { f[t2]=t1; return 1; } return 0; } int main() { int i; scanf("%d%d",&n,&m); //第一步，找到一个结构体储存边的位置 for(i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); //第二步，按边的大小排序 sort(e+1,e+m+1,cmp); //第三步，初始化 for(i=1;i<=n;i++) f[i]=i; //第四步，kruskal算法的核心 for(i=1;i<=m;i++) { //先判断两点是否连通 if(merge(e[i].u,e[i].v))//如果不连通，这条边 { cou++; sum=sum+e[i].w; } if(cou==n-1)//直到n-1条边后退出循环 break; } printf("%d",sum);//打印结果 getchar();getchar(); return 0; }这个算法也采用上面那个例子； 这个算法的思想是：
//prime算法 #include<stdio.h> int main() { int n,m,i,j,k,minn,t1,t2,t3; int e[7][7],dis[7],book[7]= {0};//这里对book数组进行初始化 int inf=999999999;//用inf（infinity的缩写）储存一我们认为的正无穷值 int cou=0,sum=0;//cou用来生成树中定点的，sum用来路径之和； //读入n和m，n表示定点个数，m表示边的条数 scanf("%d%d",&n,&m); //第一步，初始化 for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //第二步，读入边 for(i=1; i<=m; i++) { scanf("%d%d%d",&t1,&t2,&t3); e[t1][t2]=t3; e[t2][t1]=t3; } //第三步，初始化dis数组， for(i=1; i<=n; i++) dis[i]=e[1][i]; //第四步，将一号点加入树 book[1]=1; //第五步，加边 cou++; //第六步，prime算法核心 while(cou<n)//找到n-1条边 { minn=inf; for(i=1; i<=n; i++) { if(book[i]==0&&dis[i]<minn)//找下一个能走的点 { minn=dis[i]; j=i; } } book[j]=1; cou++; sum=sum+dis[j]; for(k=1; k<=n; k++) { if(book[k]==0&&dis[k]>e[j][k])//找到通向这个点的最短路 dis[k]=e[j][k]; } //扫描当前定点j所有边，在以j为中间点，更新生成树到每一个非数定点的距离 for(k=1;k<=n;k++) { printf("%d ",dis[k]); } printf("\n"); } printf("%d",sum);//打印结果 getchar(); getchar(); return 0; }