算法设计与分析 贪心算法实验(2)

《算法设计与分析 贪心算法实验(2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验7贪心算法实验(2)实验内容1.在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。假设所有认识的人一定属于同一个单位，请计算该城市有多少个单位？输入：第1行的第1个值表示总人数，第2个值表示总信息数；第2行开始为具体的认识关系信息。例：10423454858输出：单位个数。例：7源代码：#include#defineMAXV10#defineMAXE45typedefstruct{intvex1;intvex2;intweight;}edge;intmain(){voidkru

2、skal(edgee[],intenu);inti,j;edgee[MAXE],temp;intnum;printf("pleaseenterthenumberofedge!");scanf("%d",&num);printf("pleaseentertheinfoofeachedge!");for(i=0;i

3、i].weight>e[j].weight){temp=e[i];e[i]=e[j];14e[j]=temp;}}kruskal(e,num);system("pause");return0;}voidkruskal(edgee[],intenu){inti,j,k;intn1,n2,m1,m2;intvex[MAXV];for(i=1;i<=MAXV;i++)vex[i]=i;i=0;k=1;while(k

4、1!=m2){printf("%d-%d-%d",e[i].vex1,e[i].vex2,e[i].weight);if(k==enu)break;k++;for(j=0;j

5、[maxver],record=0,touched[maxver][maxver];   intcircle=0;   intFindCircle(int,int,int,int);   intmain()   {   intpath[maxver][2],used[maxver][maxver];   inti,j,k,t,min=maxright,exsit=0;   intv1,v2,num,temp,status=0;   restart:   printf("Pleaseenterthenumberofverte

6、x(s)inthegraph:");   scanf("%d",&num);   if(num>maxver

7、

8、num<0)   {   printf("Error!Pleasereinput!");   gotorestart;   }   for(j=0;j

9、   re:   printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1);   scanf("%d",&temp);   if(temp>=maxright

10、

11、temp<-1)   {   printf("Invalidinput!");   gotore;14   }   if(temp==-1)   temp=maxright;   G[j][k]=G[k][j]=temp;   u

12、sed[j][k]=used[k][j]=0;   touched[j][k]=touched[k][j]=0;   }   }   for(j=0;j