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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
why wouldn't that be a tree?

Did you mean:
1 2
2 1
0 0
-1 -1

In which case I get "is not a tree".

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

### a tree

oh, the case
1 2
1 2
0 0

1 2
2 1
0 0

-1 -1
they are different, why? the first case have two nodes '1' , '2', and two paths from node '1' to node '2'. But the second case is a cycle, one path from node '1' to node '2', and another is from node '2' to node '1'

so the output is
Case 1 is not a tree.
Case 2 is not a tree.

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
hehe, i was being dumb. of course that's not a tree.
a simple one line fix and AC.

Thanks!
Broderick

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
hi guys
could you please give me some more test case? my program (i'm using 1d array) already handle the cycle node or repeated node, but judge still give me WA.
thank you

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
1 2
1 3
2 4
2 5
2 6
2 7
3 8
8 9
9 10
10 11
11 12
12 13

why it is not a tree?

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
hello there hank. i got this prob AC, and it has not been rejected yet. my prog gives your input to be a tree, and i agree with the result.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

### 615 Is it a tree?

[cpp]
#include <iostream>
#include <stdlib.h>
using namespace std;
class node {
public:
int parent;
int self;
bool visited;
};
node pt[20000000];
class input {
public:
int from;
int to;
};
input in[10000000];
int arrayto=-1,arrayto2=0;
int x,y;
int found;
int ok;
int i,j,counter=1;
int dfs(node);
void main(void)
{
while (1)
{
for (i=0;i<=1000;i++)
{
pt.self =i;
pt.visited =false;
pt.parent =0;
}

arrayto=-1;
while (1)
{

cin>>x>>y;
if ((x==-1) && (y==-1))
exit(0);
if ((x==0) &&(y==0))
break;
in[++arrayto].from=x;
in[arrayto].to=y;
}

for (i=0;i<=arrayto;i++)
{
found=0;ok=0;
for (j=0;j<=arrayto;j++)
{
if (in.from==in[j].to)
{
found=1;
break;
}

}
if (found==0)
{
ok=1;
break;
}
}
if (arrayto==0)
if (in[0].from ==in[0].to )
{
cout<<"Case "<<counter++<<" is a tree."<<endl;
continue;
}
if (ok==1)
{
pt.visited =true;
pt.self=in.from;
}
arrayto2=0;
if (ok==1)
{
ok=dfs(pt);
}
if (ok==1)
{
for (i=0;i<=arrayto;i++)
if(pt[in.to].visited ==false)
{

ok=0;

}
if(pt[in.from].visited ==false)
{

ok=0;

}

}

if (ok==1)
cout<<"Case "<<counter++<<" is a tree."<<endl;
else
cout<<"Case "<<counter++<<" is not a tree."<<endl;

}

}

int dfs(node get)
{
int i,j,k;

for (i=0;i<=arrayto;i++)
{
if (in[i].from ==get.self )
if (pt[in[i].to].visited ==true)
{
ok=0;
return ok;
}
else
{
pt[in[i].to].parent =get.self ;
pt[in[i].to].visited =true;
ok=dfs(pt[in[i].to]);
}
}
return ok;
}

[/cpp]

o, i got a WA..please help me to test test it.
what test cases i could't pass?

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Please be carefull, the input can be like this:

input:
1 2
1
4 5
0 0

output:
Case 1 is not a tree.

Hope this helps.

LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

### 615 WA

Code: Select all

``````[pascal]program n615;
var
graph : array[1..1000] of array[1..1000] of integer;
marked : array[1..1000] of array [1..1000] of integer;
quantity : array[1..1000] of integer;
bg,nd : integer;
i,j : integer;
subgraph : integer;
max : integer;
tree : boolean;
connections : integer;
testnr : integer;
procedure dfs(x : integer);
var
i : integer;
begin
if marked[subgraph,x] = 1 then
begin
tree := false;
exit;
end;

for i:= 1 to max do
begin
if odd(graph[x,i]) then dfs(i);
end;
marked[subgraph,x] := 1;
inc(quantity[subgraph]);
end;

begin
{ assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
testnr := 1;
while true do
begin

connections := 0;
fillchar(quantity,sizeof(quantity),0);
fillchar(graph,sizeof(graph),0);
fillchar(marked,sizeof(marked),0);
max := 0;
tree := true;
max := bg;
if nd > max then max := nd;
graph[bg,nd] := 1;
while bg + nd <> 0 do
begin
graph[bg,nd] := 1;
if nd > max then max := nd;
if bg > max then max := bg;
end;
for subgraph := 1 to max do
begin
dfs(subgraph);
if not(tree) then break;
end;
for i := 1 to max do
begin
connections := 0;
for j := 1 to max do
begin
if graph[j,i] = 1 then inc(connections);
if connections > 1 then
begin
tree := false;
break;
end;
end;
if not(tree) then break;
end;
connections := 0;
for i:= 1 to max do
if quantity[i] >= connections then
begin
connections := quantity[i];
end;
for i:= 1 to max do
if (quantity[i] = connections) and (i<>head)then
begin
tree := false;
exit;
end;
for i:= 1 to max do
begin
if i = head then continue;
if (quantity[i] <> 1) and (marked[head,i] <> 1) then
begin
tree := false;
break;
end;
end;
if not tree then writeln('Case ',testnr, ' is not a tree.')
else writeln('Case ',testnr, ' is a tree.');
if bg < 0 then
begin
break;
end;
inc(testnr);
end;

end.

[/pascal]``````
Thanks
Best reguards

New(User)
New poster
Posts: 3
Joined: Sat Jan 31, 2004 11:01 am

### this judge is so distressing

because dealing with the input is much harder than solving the problem.

what's the tricky case for problem 615 is it a tree ?

New(User)
New poster
Posts: 3
Joined: Sat Jan 31, 2004 11:01 am

### 615 what's the tricky input

?

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
hello,
well, there's isn't much tricky inputs i guess. the ONLY tricky ( yet described in the problem statement) is an input with zero nodes.
input

Code: Select all

``0 0``
and the output should be trivial, tree.
the real PROBLEM is the index of nodes isn't bound to small limits. the node indices even can be >10000. so prepare for inputs:

Code: Select all

``````10006 10008 10005 10003  10005 10002 10006 10004
10005 10006  0 0
-1 -1``````
which is off course a tree.
greetings...
Istiaque Ahmed [the LA-Z-BOy]

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: 615 what's the tricky input

New(User) wrote:?
Nice post

Try:

Code: Select all

``````1 1
0 0

1 2
1 2
0 0

1 2
2 1
0 0

1 2
3 4
4 3
0 0

-1 -1
``````
Saludos,
HoraPe

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
it is not a tree... becouse tere is loop....
MIras

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm
what would be the output that the judge expects if a node points to itself? not a tree isn't it?

my code is as follows but gives WA

Code: Select all

``````#include <iostream.h>

#define SIZE 1000000

int a[SIZE], d[SIZE];

void main(void)
{
int i, last, n1, n2, pfound, cfound, istree, noparents, cnt=0;
while (1){
last=0;
istree=1;
cnt++;
while (1){
cin >> n1 >> n2;
if (n1==0 && n2==0) break;
if (n1<0 && n2<0)	break;
if (n1==n2)  istree=0;

if (istree==0)
continue;

pfound=0;
cfound=0;

for (i=0;i<last && (pfound==0 || cfound==0);i++){
if (a[i]==n1){
pfound=1;
}
if (a[i]==n2){
if (d[i]==1){
istree=0;
break;
}
else{
d[i]=1;
cfound=1;
}
}
}

if (i==last){
if (!pfound){
a[last]=n1;
d[last]=0;
last++;
}
if (!cfound){
a[last]=n2;
d[last]=1;
last++;
}
}
}

if (n1<0 && n2<0)	break;

if (istree){
noparents=0;
for (i=0;i<last && noparents<=1;i++)
if(d[i]==0 )	noparents++;
if (last>0 && noparents!=1)
istree=0;
}

if (istree)
cout << "Case " << cnt << " is a tree.";
else
cout << "Case " << cnt << " is not a tree.";
cout << endl;
}
}``````
where might be the problem be?