## 615 - Is It A Tree?

Moderator: Board moderators

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

Red Scorpion wrote:
input:
1 2
1
4 5
0 0
No, you are wrong. All the edge description must be in pair (a,b) which means there is an edge from vertex a --> b.

There is no end vertex for 1 in second line... All the input set will be of even in its number of content...

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
try not to use

Code: Select all

``array[1..1000] of array[1..1000] of integer``
becouse it will spoil your run time.. and u can get TLE...  Remember Never Give Up
Miras

ILYA
New poster
Posts: 2
Joined: Sun Sep 19, 2004 9:50 am
Location: Russian Federation

### 615 (Is it tree) - Help me (or give me input)

[pascal]
program isittree_prog;
const max=10000;
kmax=2;
type mas=array[1..max,1..kmax] of integer;
masbool=array[1..max] of byte;
var egd:mas;
nodegone:masbool;
notstop:boolean;
num:word;
casenum:longint;

{main part}
procedure isitonlypath(a:integer; b:integer);
var i:word;
cont:boolean;
begin
i:=1;
cont:=true;

while (i<=num) and cont do
begin
if (a=b) then begin
{inc(nodegone);}
cont:=false;
end
else
if egd[i,1]=a then
begin
nodegone:=1;
isitonlypath(egd[i,2], b);
end;
inc(i);
end;
end;

function isittree(var egd:mas; num:word):boolean;
var i,j:word;
k,root:integer;
fixa,a,fixb,b:integer;
istree:boolean;
begin
istree:=true;

{1: b->a & c->a - not tree}
{for i:=1 to num-1 do}
i:=1;
while (i<num) and (istree) do
begin
{fixa:=egd[i,1];}
fixb:=egd[i,2];
{for j:=i+1 to num do}
j:=i+1;
while (j<=num) and istree do
begin
b:=egd[j,2];
if (fixb=b) then
begin
istree:=false;
end;
inc(j);
end;
inc(i);
end;
{1 - end}

{2: a-root, a1-root?}
{for i:=1 to num do}
i:=1;
root:=0;
while (i<=num) and (istree) do
begin
fixa:=egd[i,1];
k:=0;
for j:=1 to num do
begin
b:=egd[j,2];
if (fixa=b) then inc(k);
end;
if (k=0) then
begin
if (root=0) then
begin
root:=fixa;
end
else
begin
if root<>fixa then
istree:=false;
end;
end;
inc(i);
end;
istree:= istree and (root<>0);
{2 - end}

{3: root->b - only 1 path}
i:=1;
{nodegone:=nodenull;}
nuller(nodegone); {nodegone:=(0,0,0...)}
while (i<=num) and (istree) do
begin
b:=egd[i,2];
if (nodegone=0) then
isitonlypath(root,b);
inc(i);
end;

i:=1;
while (i<=num) and istree do
begin
if (nodegone<>1) then istree:=false;
inc(i);
end;

{3 - end}

isittree := istree;
end;

begin
casenum:=1;
input(egd,num,notstop);
while notstop do
begin
if (num>1) then
output( isittree(egd,num) , casenum)
else
output( true, casenum );
inc(casenum);
input(egd,num,notstop);
end;

end.
[/pascal]

I always get WA. Please tell me - where I wrong! Standart input works well!
PS (sorry for my English)

ILYA
New poster
Posts: 2
Joined: Sun Sep 19, 2004 9:50 am
Location: Russian Federation
I find my bug!
[pascal]
if (num>1) then
output( isittree(egd,num) , casenum)
else
begin
if (num=0) output( true, casenum );
if (num=1) output( not (egd[1,1]=egd[1,2]), casenum );
[/pascal]
1 1 0 0

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Some sample I/O on problem 615

Although at first sight it seems quite trivial, the problem 615
finally happens to be quite tricky and hard to get ACC on.
At least that's my feeling about it.

I got ACC on July 12, 2005 ( I mention this as I read in other
threads that there has been an old judge on that problem / 615 / ).

Here is some test data for anyone who might be
still working on that problem:

INPUT

Code: Select all

``````6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

0 0

1 1 0 0

1 2 2 1 5 5 0 0

1 2
2 1
4 5
0 0

1 2
2 3
3 4
4 1
0 0

1 2 2 3 3 1 4 5 0 0

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 2 2 3 3 1 4 5 0 0

1 2
1 3
2 4
2 5
2 6
2 7
3 8
8 9
9 10
10 11
11 12
12 13
0 0

10006 10008 10005 10003  10005 10002 10006 10004
10005 10006  0 0

99006 700002 700002 880002  880002 1000001 1000001 1234567890
1234567890 22  0 0

-1 -1 ``````

OUTPUT

Code: Select all

``````Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is not a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 8 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.
Case 11 is not a tree.
Case 12 is not a tree.
Case 13 is not a tree.
Case 14 is not a tree.
Case 15 is a tree.
Case 16 is a tree.
Case 17 is a tree.``````

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
hello guys
i thing the problem is not so hard and what i did is
suppose the following input (taken from sample I/O)

Code: Select all

``````6 8  5 3  5 2  6 4
5 6  0 0
``````
lets treat 6 as 1 and 8 as 2, so we have an edge 1->2
now comes 5 3 treat 5 as 3, and 3 as 4 so the edge is 3->4...
coms 5 2 now since 5 is already NUMBERED, so treat 2 as 5
so the edge is 3->5
coms 6 4, now we to number 4 as 6
so edge is 1->6
coms 5 6, edge is 3->1
i thing u understand what i mean...(assign a unique number when a "new" number comes in the graph)
i assumed there are at most 500 nodes(which worked fine).
so the big part is to handle the input number in UR way and never forget to check whether the graph forms "a" tree(by DFS(i implemented) or BFS, etc. )
also u would find IN_DEGREE of a vertex is pretty useful.
good luck regards
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:

### Re: Some sample I/O on problem 615

Sedefcho wrote: 1 1 0 0

1 2
1 2
0 0

...
Case 10 is not a tree.
Case 11 is not a tree.
[/code]
hey man, I think that's a wrong case. Because 1 1 0 0 is a tree with one root. 1 2 1 2 0 0 is simply a tree with nodes 1 and 2, with 1 being the parent of 2.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world
Then, what shall we do? :lol:
All living things are amazing thing.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world
hmm... maybe it`s too late, but I`ll give you a input.

Code: Select all

``0 0``
All living things are amazing thing.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

### 615

My code is

Code: Select all

``````#include<iostream.h>
int a,cn=0,chk,ml;
void treechk(int i){
chk[i] = 1;
int j;
for(j = 0; j<1000; j++){
if(a[i][j] > 0){
if(chk[j] == 1){
cout << "Case " << cn+1 << " is not a tree." << endl;
return;
ml=1;
}
treechk(j);
}
}return;
}
void main(){
int x,y,t=0,i,j,m;
while(cin >> x >> y){
if(x!=-1&&y!=-1){
if(x==0 && y==0){
if(t==0){
treechk(0);
for(i = 0; i<1000; i++){
if(chk[i]==1) m=chk[i];
}for(i = 0; i<m; i++){
if(chk[i] == 0){
cout << "Case " << cn+1 << " is not a tree." << endl;
ml=1;
break;
}
}
if(ml==0) cout << "Case " << cn+1 << " is a tree." << endl;
cn++;
}
for(i = 0; i<1000; i++){
for(j = 0; j<1000; j++){
a[i][j] = 0;
}
chk[i] = 0;
}
t=0;
ml=0;
m=0;
}else{
if(a[x-1][y-1] == 1 || a[y-1][x-1] == 1){
t=1;
cout << "Case " << cn+1 << " is not a tree." << endl;
}else{
a[x-1][y-1]=1;
a[y-1][x-1]=2;
}
}
}else break;
}
}``````
Plz... plz help me...
What`s the mistake of my code?
All living things are amazing thing.

LPH
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am
I put in some of test cases to your program and found out some problem in your code:

(1) in some of the input your programs gives multiple line of output. for example, with this input taken from sample input:

Code: Select all

``````8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0``````

Code: Select all

``````Case 1 is not a tree.
Case 1 is a tree.``````
and with this input:

Code: Select all

``1 2 1 3 2 4 2 5 2 6 2 7 3 8 8 9 9 10 10 11 11 12 12 13 0 0``

Code: Select all

``````Case 2 is not a tree.
Case 2 is not a tree.
Case 2 is a tree.``````
where these two inputs are both trees.

(2) with some of the input, your counter won't increase. for example,

Code: Select all

``````1 2 1 2 0 0
1 2 2 1 0 0
1 2 3 4 4 3 0 0``````
your program produces correct result with these cases (not a tree), but the counter is halted (stay at the same number).

(3) your program didn't terminate when the end of data tag isn't -1. The problem statement says:
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers.
Another thing I found out when I look into your program: the node number could be greater then 10000(refers from this post and this post), where your code can only handle up to 1000.
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Whats wrong with my code? I used array size 5400 , still I found the niode numbers are evn greater than 5400 ...using arrays larger than that caused me MLE ... now, can anyone help me ???

Code: Select all

``````#include<stdio.h>
#include<memory.h>

#define MAX 5400

bool a[MAX][MAX];
int b[MAX];

int findroot(int max)
{
int i,j;
int nor=0,root=0,sum;
for(i=1;i<=max;i++)
{
if(b[i])
{
sum=0;
for(j=1;j<=max;j++)
{
if(a[j][i])
{
sum++;
}
}
if(sum==0)
{
root=i;
nor++;
}
if(sum>1)
{
return -1;
}
if(nor>1)
{
return -1;
}
}
}
return root;
}

int DFS(int n,int max)
{
int i,j;
if(b[n]>1)
{
return -1;
}
b[n]++;
for(i=1;i<=max;i++)
{
if(a[n][i])
{

j=DFS(i,max);
if(j<0)
{
return j;
}
}
}
return 1;
}

int isVisited(int max)
{
int i;
for(i=1;i<=max;i++)
{
if(b[i]==1)
{
return -1;
}
}
return 1;
}

int main(void)
{
int m,n,max,t=0;
while(1)
{
scanf("%d%d",&m,&n);
if(m<0 || n<0)
{
break;
}
t++;
if(m==0 && n==0)
{
printf("Case %d is not a tree.\n",t);
continue;
}
max=0;
memset(a,false,sizeof(a));
memset(b,0,sizeof(b));

a[m][n]=true;
b[m]=1;
b[n]=1;

if(m>max)
{
max=m;
}
if(n>max)
{
max=n;
}

while(1)
{
scanf("%d%d",&m,&n);
if(m==0 && n==0)
{
break;
}
a[m][n]=true;
b[m]=1;
b[n]=1;
if(m>max)
{
max=m;
}
if(n>max)
{
max=n;
}
}
printf("Case %d is ",t);
int root=findroot(max);
if(root<=0)
{
printf("not a tree.\n");
continue;
}
int check=DFS(root,max);
if(check<0)
{
printf("not a tree.\n");
continue;
}
check=isVisited(max);
if(check<0)
{
printf("not a tree.\n");
continue;
}
printf("a tree.\n");

}
return 0;
}

``````
Syed Ishtiaque Ahmed Kallol
CSE,BUET

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm
Try this:
1 2 3 4 0 0
-1 -1
It's not a tree

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm
You can also try:
0 0
-1 -1

it's a tree -
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.

phoenix7
New poster
Posts: 5
Joined: Fri Oct 07, 2005 11:21 pm
Location: Tehran, IRAN
Contact:

### 615 WA!

Can anyone give me a test case for which my code outputs wrong answer?

Code: Select all

``````#include <cmath>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <string>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#ifndef ONLINE_JUDGE
#define show(x)			cout << #x << " = " << x << endl
#else
#define show(x)
#endif
#define FOR(i, n)		for(int i = 0; i < n; i ++)
#define FORE(i, m, n)	for(int i = m; i < n; i ++)

int indegree;
bool used;
int parent;

int main() {
#ifndef ONLINE_JUDGE
freopen("IsItATree.in", "r", stdin);
#endif

int x, y;

int tt = 0;
while(cin >> x >> y, x+y >= 0) {
tt ++;

if(x+y == 0) {
cout << "Case " << tt << " is a tree." << endl;
continue;
}

memset(indegree, 0, 1000000*sizeof(int));
memset(used, 0, 1000000*sizeof(bool));
memset(parent, 0, 1000000*sizeof(int));

int v = (x == y ? 1 : 2), e = 1;
int grandparent = x;

parent[y] = x;

indegree[y] ++;
used[x] = used[y] = true;
while(cin >> x >> y, x+y) {
//cout << x << " " << y << endl;
e ++;
if(!used[x])
v ++;
if(!used[y])
v ++;

int p = x;
while(parent[p])
p = parent[p];
//show(p);

int n = x;
while(parent[n]) {
n = parent[n];
if(n != p)
parent[n] = p;
}
if(y != p)
parent[y] = p;

indegree[y] ++;
used[x] = used[y] = true;
}

//show("gholi");

bool ok = true;
int zero = 0;
FOR(i, 1000000) {
if(!used[i])
continue;

if(indegree[i] == 0)
zero ++;
else if(indegree[i] > 1) {
ok = false;
break;
}
}

/*FOR(i, 1000000)
if(used[i])
cout << i << " " << parent[i] << endl;
*/

bool parentfail = false;
FOR(i, 1000000)
if(used[i] && parent[i] != grandparent) {
parentfail = true;
break;
}
//show(zero);
if(v == e + 1 && ok && zero == 1 && !parentfail)
cout << "Case " << tt << " is a tree." << endl;
else
cout << "Case " << tt << " is not a tree." << endl;
}

return 0;
}
``````