615 - Is It A Tree?

Moderator: Board moderators

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

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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, 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]

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
check with this:

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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
Case 1 is a tree

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
but is it really a tree? is there a unique sequence of directed edges from the root to each node?

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: 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]

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

bigger input

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

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan
Before the judge, I use array[100][100], can get 100 nodes, you means
it have 100000 nodes...?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
why so much trouble?
just use two linear arrays. one for parent, one for child.
and then check.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 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.

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

AC

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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
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.

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

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