Guys,this problem is making me crazy. I cant think even on other things. I have gone through all the post related with 615. plz help me why this is giving me WA.
my algo:
1. search the adjacent matrix for root with in degree.(which in degree is 0?)
2. then see for multiple root
3. then finding the distance of all node from root using floyed warshall( considering a connected edge weighted as 1)
I know its a long code. h\but plz help me.
Code: Select all
#include<iostream>
using namespace std;
int w[501][501];
int d[501][501];
int n;
int vertex[501];
int len;
void floyd()
{
int i, j, k;
for( i = 1 ; i <= n ; i++)
{
for( j = 1 ; j <= n ; j++)
{
if(w[i][j] != 0 )
d[i][j] = w[i][j];
else d[i][j] = 999999; // 999999 consider as infinite
}
}
for(i =1 ; i <= n ; i++)
d[i][i] = 0;
for( k = 1 ; k <= n ; k++)
{
for( i = 1 ; i <= n ;i++)
{
for( j =1 ; j <= n ; j++)
{
if(d[i][k]+d[k][j] < d[i][j])
{
d[i][j] = d[i][k]+d[k][j];
}
}
}
}
}
void init()
{
int j,i;
for( i = 1 ; i <= 501 ; i++)
{
for( j = 1 ; j <= 501 ; j++)
{
w[i][j]=0;
}
}
for(i=0;i<501;i++)
vertex[i]= -5;
}
int find(int x)
{
for(int i=1;i<501;i++)
{
if(vertex[i]==x)
{
return i;
}
}
return -5;
}
int main()
{
int root,x,y,nn,root_no,temp_x,temp_y,flag,cas=1;
register int i,j;
// freopen("in_615.txt","r",stdin);
while(scanf("%d %d",&x,&y) && x!=-1 && y!=-1)
{
init();
if(x==y)
{
if(x==0)
printf("Case %d is not a tree.\n",cas);
else
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}
vertex[1]=x;
vertex[2]=y;
w[1][2]=1;
i=3;
flag=0;
while(scanf("%d %d",&x,&y) && x!=0 && y!=0)
{
temp_x=find(x);
if(temp_x== -5)
{
vertex[i]=x;
temp_x=i;
i++;
}
temp_y=find(y);
if(temp_y== -5)
{
vertex[i]=y;
temp_y=i;
i++;
}
if(w[temp_x][temp_y]!=1)
w[temp_x][temp_y]=1;
else
flag=1;
}
if(flag==1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}
len=i;
n=len-1;
root=0;root_no=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(w[j][i]!=0)
break;
}
if(j==n+1)
{
root_no=i;
root++;
}
}
if(root!=1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}
flag=0;
for(i=1;i<=n;i++)
{
root=0;
for(j=1;j<=n;j++)
{
if(w[j][i]!=0)
root++;
}
if(root!=1)
{
if(root_no!=i)
flag=1;
//continue;
}
}
if(flag==1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}
floyd();
flag=0;
for(i=1;i<=n;i++)
{
if(d[root_no][i]==999999)
{
flag=1;
break;
}
}
if(flag!=1)
{
printf("Case %d is a tree.\n",cas);
cas++;
}
else
{
printf("Case %d is not a tree.\n",cas);
cas++;
}
}
return 0;
}