615 - Is It A Tree?

[Rajib]

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]

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

[ILYA]

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

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

[Sedefcho]

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]

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.
sorry for long read...
good luck
regards
RSS

[jjtse]

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]

Then, what shall we do? :lol:

[scidong]

hmm... maybe it`s too late, but I`ll give you a input.

Code: Select all

0 0

[scidong]

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?

[LPH]

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.

[Kallol]

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;
}

[WRJ]

Try this:
1 2 3 4 0 0
-1 -1
It's not a tree

[WRJ]

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]

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;
}