刚接触图论,代码是参考别人的,但是运行结果不对,请求指教
//未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn,请你给出每两个湖泊之间的相连关系。#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 15
struct vertex
{
int degree;
int index;
}v[N];
int cmp( const void *a,const void *b )
{
return ((vertex *)b)->degree - ((vertex *)b)->degree;
}
int main()
{
int r,k,p,q;
int i,j;
int d1;
int T,n;
int Edge[N][N],flag;
scanf( "%d",&T );
while( T-- )
{
scanf( "%d",&n );
for( i = 0; i < n; i++ )
{
scanf( "%d",&v[i].degree );
v[i].index = i;
}
memset( Edge,0,sizeof( Edge ) );
flag = 1;
for( k = 0; k < n&&flag; k++ )
{
qsort( v+k,n-k,sizeof( vertex ),cmp );
i = v[i].index;
d1 = v[k].degree;
if( d1 > n - k - 1 ) flag = 0;
for( r = 1; r <= d1&&flag; r++)
{
j = v[k+r].index;
if( v[k+r].degree <= 0 ) flag = 0;
v[k+r].degree--;
Edge[i][j] = Edge[j][i] = 1;
}
}
if( flag )
{
puts( "YES" );
for( p = 0; p < n; p++ )
{
for( q = 0; q < n; q++ )
{
if( q )
printf( " " );
printf( "%d",Edge[p][q] );
}
puts( "\n" );
}
}
else puts( "NO" );
if( T ) puts( "\n" );
}
return 0;
}