![:x](./images/smilies/icon_mad.gif)
Could anyone send me some test data??
Thank you very much
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct edges
{
int v1;
int v2;
double length;
}Edge;
int comp(const void *a,const void *b)
{
if (((Edge *)a)->length > ((Edge *)b)->length) return 1;
if (((Edge *)a)->length < ((Edge *)b)->length) return -1;
return 0;
}
int link[750];
int Find(int element)
{
if(link[element]==element)
return element;
else
return Find(link[element]);
}
void UnionSet(int set1, int set2)
{
link[set2]=set1;
}
void Union(int element1, int element2)
{
UnionSet(Find(element1),Find(element2));
}
void Kruskal(Edge *e,int nt,int ne,int nb)
{
int y=0;
qsort(e,ne,sizeof(Edge),comp);
nt-=nb;
while(nt>1)
{
if(Find(e[y].v1)!=Find(e[y].v2))
{
printf("%d %d\n",e[y].v1+1,e[y].v2+1);
Union(e[y].v1,e[y].v2);
nt--;
}
y++;
}
}
int main()
{
Edge e[300000];
int pos[750][2],NumT,x,y,z,count,NumE,NumB,t1,t2;
scanf("%d",&count);
for(x=0;x<count;x++)
{
/* get data */
scanf("%d",&NumT);
for(y=0;y<NumT;y++)
{
scanf("%d %d",&pos[y][0],&pos[y][1]);
link[y]=y;
}
scanf("%d",&NumB);
if((NumB+1)>=NumT)
{
for(y=0;y<NumB;y++)
{
scanf("%d %d",&t1,&t2);
}
printf("No new highways need\n\n");
continue;
}
for(y=0;y<NumB;y++)
{
scanf("%d %d",&t1,&t2);
Union(t1-1,t2-1);
}
/* compute the distance */
NumE=0;
for(y=0;y<NumT;y++)
for(z=y+1;z<NumT;z++)
{
e[NumE].v1=y;
e[NumE].v2=z;
e[NumE++].length=sqrt((pos[y][0]-pos[z][0])*(pos[y][0]-pos[z][0])+(pos[y][1]-pos[z][1])*(pos[y][1]-pos[z][1]));
}
Kruskal(e,NumT,NumE,NumB);
printf("\n");
}
return 0;
}
[/cpp]