## 615 - Is It A Tree?

Moderator: Board moderators

### 615 - Is It A Tree?

My method is described as follows:

1. According the input data, for each element, I defined two integer which are the number of edge pointing to that node ( say it A ) and the number of edge where that node points( say it B).

If A = 0, then that node is defined as root. Therefore, if finding root again, this is not a tree. Of course, if no root, this is also not a tree.

If A >= 2, then this is not a tree.

There is another occasion. That is when there are two graph, one is a circuit and the other is a tree. Then the result is wrong following the rules above. Therefore, after checking the rules shown above, I trace each node from the root, and get the number of checked node. If the number of the checked node is not equal to the number of nodes, then the graph must be separated and this is not a tree. Otherwise, it does.

However, I still get wrong answer ... >< ..
I don't know what mistake I make or I ignore some facts.

Plz help me >< ...

DemonCris
New poster

Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

### 615

The code always gets WA. Where's the bug?
[c]
#include<stdio.h>
#include<stdlib.h>
#define YES 1
#define NO 0
void main(void)
{
int count,found,a,b,x,y,root,error;
struct node
{
int name;
int in,out;
}nodes[10000];
for(count=1;;count++)
{
x=0;
while(1)
{
scanf("%d %d",&a,&b);
if(a<0 && b<0)
exit(0);
if(a==0 && b==0)
break;
for(y=0;y<x;y++)
if(a==nodes[y].name)
{
nodes[y].out++;
break;
}
if(y==x)
{
nodes[x].name=a;
nodes[x].in=0;
nodes[x].out=1;
x++;
}
for(y=0;y<x;y++)
if(b==nodes[y].name)
{
nodes[y].in++;
break;
}
if(y==x)
{
nodes[x].name=b;
nodes[x].in=1;
nodes[x].out=0;
x++;
}
}
error=NO;
for(y=0,root=-1;y<x;y++)
if(nodes[y].in==0)
if(root==-1)
root=nodes[y].name;
else
{
error=YES;
break;
}
if(error)
{
printf("Case %d is not a tree.\n",count);
continue;
}
for(y=0;y<x;y++)
if(nodes[y].name==root)
;
else if(nodes[y].in!=1)
break;
if(y==x)
printf("Case %d is a tree.\n",count);
else
printf("Case %d is not a tree.\n",count);
}
}
[/c]
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

check with this:

1 2 3 4 4 3 0 0
-1 -1
Picard
Learning poster

Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary

Case 1 is a tree
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

but is it really a tree? is there a unique sequence of directed edges from the root to each node?
Picard
Learning poster

Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary

So it's not enough for me to just check the in/out degrees?Do I need to check the in/out degrees by BFS?
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 615 New Judge

Before the New Judge, I get a AC , but after the New Judge
I get a WA , can anyone can help me ~ ?

~ 2002 / 7 / 11 ~[/cpp]
T.T.
New poster

Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

### bigger input

I had my program rejected after rejudge too, but got AC after adjusting for bigger input (no. of nodes 10000 -> 100000).
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Before the judge, I use array[100][100], can get 100 nodes, you means
it have 100000 nodes...?
T.T.
New poster

Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

Sorry, I was referring to the maximum nodenumber. I don't know about the maximum number of nodes, but it could of course be also increased to above 100.
I don't use a matrix to store edges, so I can't tell.
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

why so much trouble?
just use two linear arrays. one for parent, one for child.
and then check.
Subeen
Experienced poster

Posts: 127
Joined: Tue Nov 06, 2001 2:00 am

1 2 2 3 3 1 4 5 0 0

it should be "not a tree". Such cases were a topic in the old message board long ago.

I don't know if there is any limit for the node numbers (except the limits of "integer"), so I stored the numbers in another array and did two lookups on every edge.

Christian Schuster
Learning poster

Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

### AC

thanks, after test the input, I get AC again&#65374;
T.T.
New poster

Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

I'd hate to post code here, but I can't seem to find the bug...it's driving
me crazy! (Btw, this codes passes all the tests posted to this board,
but still gets WA).
Last edited by broderic on Thu Aug 08, 2002 10:32 pm, edited 1 time in total.
broderic
New poster

Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

### input

you can try it:
1 2
1 2
0 0

-1 -1
of course, it's output is
Case 1 is not a tree
T.T.
New poster

Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

Next