现在有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
",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("
");
}
printf("%d",sum);//打印结果
getchar();
getchar();
return 0;
}