## 615 - Is It A Tree?

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

payton1
New poster
Posts: 5
Joined: Mon Oct 02, 2006 10:31 pm

### 615 WA

Anyone can tell me what's wrong in my code?I test every input here,and all get right output.But I get the wrong answer.

Code: Select all

//Is It A Tree?
#include <iostream>
using namespace std;

int main()
{
int* fr;
bool* ex;
int f=0;
int t=0;
int root=0;
int ca=0;
int num=0;
int st=0;
int now=0;
const int max=1000;
bool istree=true;
cin>>f;
cin>>t;
while(f!=-1||t!=-1)
{
fr=new int[max];
ex=new bool[max];
istree=true;
root=0;
num=0;
ca++;
while(f!=0||t!=0)
{
num++;
if(fr[t]>0||f==t)
{
istree=false;
break;
}
fr[t]=f;
ex[f]=true;
ex[t]=true;
cin>>f;
cin>>t;
}
if(istree==true)
{
for(int i=0;i<max;i++)
{
if(ex[i]==true&&fr[i]<=0)
{
if(root!=0)
{
istree=false;
break;
}
else
root=i;
}
st=i;
now=i;
while(fr[now]>0)
{
if(fr[now]==st)
{
istree=false;
break;
}
now=fr[now];
}
}
}
if(istree&&root>0&&num!=0)
cout<<"Case "
<<ca
<<" is a tree."
<<endl;
else
{
while(f!=0||t!=0)
{
cin>>f;
cin>>t;
}
cout<<"Case "
<<ca
<<" is not a tree."
<<endl;
}
delete [] fr;
delete [] ex;
fr=0;
ex=0;
cin>>f;
cin>>t;
}
return 0;
}

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### Re: Oh gosh-! I can`t solve this problem- (615)

try this
input:

Code: Select all

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

1 2 1 3 2 4 2 5 2 6 2 7 3 8 8 9 9 10 10 11 11 12 12 13 0 0

1 2 0 0

1 2 2 1 0 0

1 2 3 4 0 0
1 2  2 4  2 5  2 6  1 3  3 6  0 0

100008 200008 10008 30000 0 0
-1 -1

Code: Select all

output:
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.
hope it helps
''I want to be most laziest person in the world''

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### Re: 615 - Is It A Tree?

i think you have given one extra output.
there are nine cases in your input.
fahim
#include <smile.h>

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: Some sample I/O on problem 615

Sedefcho wrote:Although at first sight it seems quite trivial, the problem 615
finally happens to be quite tricky and hard to get ACC on.
At least that's my feeling about it.

I got ACC on July 12, 2005 ( I mention this as I read in other
threads that there has been an old judge on that problem / 615 / ).

Here is some test data for anyone who might be
still working on that problem:

INPUT

Code: Select all

0 0

99006 700002 700002 880002  880002 1000001 1000001 1234567890
[color=#BF0000]1234567890[/color] 22  0 0

-1 -1

You can safely assume that node number is less than 1000002.
Mak
Help me PLZ!!

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

### Re: 615 - Is It A Tree?

//code removed after AC

why am i getting WA...
Last edited by codeworrior on Tue Jan 12, 2010 4:27 pm, edited 1 time in total.

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

### 615 is it a tree??

//code removed after AC

why am i getting WA...

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 615 - Is It A Tree?

See previous posts..
Your code fails on turcse143's test cases..

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

### Re: 615 - Is It A Tree?

yes corrected it ...got AC..thanks..

AmitMist
New poster
Posts: 6
Joined: Wed Feb 18, 2009 10:20 pm

### Re: 615 - Is It A Tree?

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;
}

sajidzaman
New poster
Posts: 1
Joined: Wed Dec 07, 2011 7:42 am
Contact:

### Re: 615 - Is It A Tree?

Hello everyone,

Is it possible to find the judges test input? because as far as i have tested with the inputs given in this thread, my program is working fine.

But on submitting it says wrong answer. I would like to get more inputs to test my program.

Regards
Sajid

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### 615 - Is It A Tree?

why WA ?
I have tried for many inputs which gives correct ans ...
I can't find those inputs which gives WA ..

Code: Select all

//code removed
Last edited by shatil_cse on Thu May 03, 2012 10:16 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 615 - Is It A Tree?

Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### Re: 615 - Is It A Tree?

brianfry713 wrote:Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.
U are really a great helper .
I got my mistakes but when I modified my code I got TLE .............
I think the process I chose is not good for this problem .

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 615 - Is It A Tree?

Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### Re: 615 - Is It A Tree?

brianfry713 wrote:Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.

thanks
Actually I don't have knowledge about c++ map .
But I got accepted by using a array which contains the parent as value & child as index . Then i make sure that all nodes are reachable from the root & it takes .008 sec.