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

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

615 - Is It A Tree?

Post by DemonCris » Tue May 21, 2002 7:09 pm

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

Post by htl » Thu Jul 04, 2002 5:50 pm

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:

Post by Picard » Thu Jul 04, 2002 6:01 pm

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

Post by htl » Thu Jul 04, 2002 6:40 pm

The answer is:
Case 1 is a tree

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

Post by Picard » Thu Jul 04, 2002 7:02 pm

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

Post by htl » Sat Jul 06, 2002 12:07 pm

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

Post by T.T. » Thu Jul 11, 2002 8:02 am

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

Post by xenon » Thu Jul 11, 2002 8:45 am

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

Post by T.T. » Thu Jul 11, 2002 11:06 am

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

Post by xenon » Thu Jul 11, 2002 11:38 am

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
Location: Bangladesh
Contact:

Post by Subeen » Sat Jul 13, 2002 11:49 pm

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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Mon Jul 15, 2002 12:52 am

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.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

AC

Post by T.T. » Fri Jul 19, 2002 2:22 pm

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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Tue Aug 06, 2002 9:51 pm

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

Post by T.T. » Wed Aug 07, 2002 8:02 am

you can try it:
1 2
1 2
0 0

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

Post Reply

Return to “Volume 6 (600-699)”