615 - Is It A Tree?

[DemonCris]

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 >< ...

[htl]

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]

[Picard]

check with this:

1 2 3 4 4 3 0 0
-1 -1

[htl]

The answer is:
Case 1 is a tree

[Picard]

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

[htl]

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?

[T.T.]

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]

[xenon]

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

[T.T.]

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

[xenon]

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.

[Subeen]

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

[Christian Schuster]

What is your output for

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.

[T.T.]

thanks, after test the input, I get AC again&#65374;

[broderic]

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).

[T.T.]

you can try it:
1 2
1 2
0 0

-1 -1
of course, it's output is
Case 1 is not a tree