615 - Is It A Tree?

[payton1]

Anyone can tell me what's wrong in my code?I test every input here,and all get right output.But I get the wrong answer.

Code: Select all

//Is It A Tree?
#include <iostream>
using namespace std;

int main()
{
	int* fr;
	bool* ex;
	int f=0;
	int t=0;
	int root=0;
	int ca=0;
	int num=0;
	int st=0;
	int now=0;
	const int max=1000;
	bool istree=true;
	cin>>f;
	cin>>t;
	while(f!=-1||t!=-1)
	{
		fr=new int[max];
		ex=new bool[max];
		istree=true;
		root=0;
		num=0;
		ca++;
		while(f!=0||t!=0)
		{
			num++;
			if(fr[t]>0||f==t)
			{
				istree=false;
				break;
			}
			fr[t]=f;
			ex[f]=true;
			ex[t]=true;
			cin>>f;
			cin>>t;
		}
		if(istree==true)
		{
			for(int i=0;i<max;i++)
			{
				if(ex[i]==true&&fr[i]<=0)
				{
					if(root!=0)
					{
						istree=false;
						break;
					}
					else
						root=i;
				}
				st=i;
				now=i;
				while(fr[now]>0)
				{
					if(fr[now]==st)
					{
						istree=false;
						break;
					}
					now=fr[now];
				}
			}
		}
		if(istree&&root>0&&num!=0)
			cout<<"Case "
				<<ca
				<<" is a tree."
				<<endl;
		else
		{
			while(f!=0||t!=0)
			{
				cin>>f;
				cin>>t;
			}
			cout<<"Case "
				<<ca
				<<" is not a tree."
				<<endl;
		}
		delete [] fr;
		delete [] ex;
		fr=0;
		ex=0;
		cin>>f;
		cin>>t;
	}
	return 0;
}

[turcse143]

try this
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

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

1 2 0 0

1 2 2 1 0 0

1 2 3 4 0 0
1 2  2 4  2 5  2 6  1 3  3 6  0 0

100008 200008 10008 30000 0 0
-1 -1

Code: Select all

output:
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.

hope it helps

[smilitude]

i think you have given one extra output.
there are nine cases in your input.

[mak(cse_DU)]

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

0 0









99006 700002 700002 880002  880002 1000001 1000001 1234567890
[color=#BF0000]1234567890[/color] 22  0 0 

-1 -1 

You can safely assume that node number is less than 1000002.

[codeworrior]

//code removed after AC

why am i getting WA...

[codeworrior]

//code removed after AC


why am i getting WA...
thanks in advance

[helloneo]

See previous posts..
Your code fails on turcse143's test cases..

[codeworrior]

yes corrected it ...got AC..thanks..

[AmitMist]

Guys,this problem is making me crazy. I cant think even on other things. I have gone through all the post related with 615. plz help me why this is giving me WA.
my algo:
1. search the adjacent matrix for root with in degree.(which in degree is 0?)
2. then see for multiple root
3. then finding the distance of all node from root using floyed warshall( considering a connected edge weighted as 1)
I know its a long code. h\but plz help me.

Code: Select all

#include<iostream>

using namespace std;

int w[501][501];

int d[501][501];
int n; 
int vertex[501];
int len;


void floyd()
{
	int i, j, k;
	for( i = 1 ; i <= n ; i++)
	{
		for( j = 1 ; j <= n ; j++)
		{
			if(w[i][j] != 0 )
				d[i][j] = w[i][j];
			
			else d[i][j] = 999999; // 999999 consider as infinite
			
		
		}
	}

	for(i =1 ; i <= n ; i++)
		d[i][i] = 0;
	
	for( k = 1 ; k <= n ; k++)
	{
		for( i = 1 ; i <= n ;i++)
		{
			for( j =1 ; j <= n ; j++)
			{
				if(d[i][k]+d[k][j] < d[i][j])
				{
					d[i][j] = d[i][k]+d[k][j];
				
				}
			}
		}
	}
	
}


void init()
{
	int j,i;
	for( i = 1 ; i <= 501 ; i++)
	{
		for( j = 1 ; j <= 501 ; j++)
		{
			w[i][j]=0;
		}
	}

	for(i=0;i<501;i++)
			vertex[i]= -5;
}

int find(int x)
{
	for(int i=1;i<501;i++)
	{
		if(vertex[i]==x)
		{
			return i;
		}
	}

	return -5;
}


int main()
{

	int root,x,y,nn,root_no,temp_x,temp_y,flag,cas=1;
	register int i,j;
	
//	freopen("in_615.txt","r",stdin);
	
	while(scanf("%d %d",&x,&y) && x!=-1 && y!=-1)
	{
		init();
		if(x==y)
		{
			if(x==0)
				printf("Case %d is not a tree.\n",cas);
			else
				printf("Case %d is not a tree.\n",cas);
			
			cas++;
			continue;
		}
		
		vertex[1]=x;
		vertex[2]=y;
		w[1][2]=1;
	

		i=3;
		flag=0;
		while(scanf("%d %d",&x,&y) && x!=0 && y!=0)
		{
			temp_x=find(x);
			if(temp_x== -5)
			{
				vertex[i]=x;
				temp_x=i;
				i++;
			}
			temp_y=find(y);
			if(temp_y== -5)
			{
				vertex[i]=y;
				temp_y=i;
				i++;
			}
			if(w[temp_x][temp_y]!=1)
				w[temp_x][temp_y]=1;
			else
				flag=1;
			

		}
		if(flag==1)
		{
			printf("Case %d is not a tree.\n",cas);
			cas++;
			continue;
		}

		len=i;
		n=len-1;
		root=0;root_no=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(w[j][i]!=0)
					break;
			}
			if(j==n+1)
			{
				root_no=i;
				root++;
			}
		}
		if(root!=1)
		{
			printf("Case %d is not a tree.\n",cas);
			cas++;
			continue;
		}
		flag=0;

		for(i=1;i<=n;i++)
		{
			root=0;
			for(j=1;j<=n;j++)
			{
				if(w[j][i]!=0)
					root++;
			}
			if(root!=1)
			{
				if(root_no!=i)
					flag=1;
				//continue;
			}
		}
		if(flag==1)
		{
			printf("Case %d is not a tree.\n",cas);
			cas++;
			continue;
		}
		
		floyd();
		flag=0;

		for(i=1;i<=n;i++)
		{
			if(d[root_no][i]==999999)
			{
				flag=1;
				break;
			}
		}
		if(flag!=1)
		{
			printf("Case %d is a tree.\n",cas);
			cas++;
		}
		else
		{
			printf("Case %d is not a tree.\n",cas);
			cas++;
		}

	}
	


	
	return 0;
}

[sajidzaman]

Hello everyone,

Is it possible to find the judges test input? because as far as i have tested with the inputs given in this thread, my program is working fine.

But on submitting it says wrong answer. I would like to get more inputs to test my program.

Regards
Sajid

[shatil_cse]

why WA ?
I have tried for many inputs which gives correct ans ...
I can't find those inputs which gives WA ..

Code: Select all

//code removed 

[brianfry713]

Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.

[shatil_cse]

Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.

U are really a great helper .
I got my mistakes but when I modified my code I got TLE .............
I think the process I chose is not good for this problem .

[brianfry713]

Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.

[shatil_cse]

Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.

thanks
Actually I don't have knowledge about c++ map .
But I got accepted by using a array which contains the parent as value & child as index . Then i make sure that all nodes are reachable from the root & it takes .008 sec.