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 >< ...
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 >< ...
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]
[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]
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]
I get a WA , can anyone can help me ~ ?
~ 2002 / 7 / 11 ~[/cpp]
bigger input
I had my program rejected after rejudge too, but got AC after adjusting for bigger input (no. of nodes 10000 -> 100000).
-
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 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).
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.