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

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

For your correction...

Post by Rajib » Sun Jun 20, 2004 4:19 pm

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

Post by miras » Sat Jul 10, 2004 11:51 am

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...
:evil: :lol:
Remember Never Give Up
Regrads
Miras

User avatar
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)

Post by ILYA » Sun Sep 19, 2004 10:06 am

[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)

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

Post by ILYA » Tue Sep 21, 2004 5:25 pm

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]
I forgot about this input:
1 1 0 0

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

Some sample I/O on problem 615

Post by Sedefcho » Tue Jul 12, 2005 5:50 pm

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:

Post by I LIKE GN » Thu Sep 01, 2005 8:29 pm

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 :wink:
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.
sorry for long read...
good luck :wink:
regards
RSS
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
Location: Nevada, US
Contact:

Re: Some sample I/O on problem 615

Post by jjtse » Thu Oct 27, 2005 10:22 pm

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

Post by scidong » Sun Feb 19, 2006 10:41 am

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

Post by scidong » Sun Feb 19, 2006 10:43 am

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

Post by scidong » Sun Feb 19, 2006 10:51 am

My code is

Code: Select all

#include<iostream.h>
int a[1000][1000],cn=0,chk[1000],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.
一八???

User avatar
LPH
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am

Post by LPH » Sat Feb 25, 2006 12:40 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
your program outputs

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
your program outputs

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Aug 02, 2006 12:18 pm

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
Bangladesh

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by WRJ » Wed Aug 30, 2006 8:22 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

Post by WRJ » Wed Aug 30, 2006 8:27 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!

Post by phoenix7 » Wed Sep 20, 2006 6:27 pm

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[1000000];
bool used[1000000];
int parent[1000000];

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;
}
-- Mohammad
do you Python?

Post Reply

Return to “Volume 6 (600-699)”