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
Location: Canada

Post by broderic » Wed Aug 07, 2002 5:33 pm

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

Post by T.T. » Thu Aug 08, 2002 5:16 am

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
Location: Canada

Post by broderic » Thu Aug 08, 2002 10:31 pm

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

Post by arc16 » Mon Sep 02, 2002 2:34 am

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Oct 22, 2002 3:06 pm

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?

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Tue Oct 22, 2002 7:22 pm

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?

Post by SilVer DirectXer » Fri Apr 11, 2003 6:08 am

[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

Post by Red Scorpion » Wed May 07, 2003 12:20 pm

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

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

615 WA

Post by LeoST » Fri Jan 16, 2004 6:25 pm

Please help me to find bugs in my code

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;
  head : 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);
  }read(bg,nd);
  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;
  head := 0;
  if nd > max then max := nd;
  graph[bg,nd] := 1;
  while bg + nd <> 0 do
    begin
      read(bg,nd);
      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];
        head := 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;
  read(bg,nd);
  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);
 { readln;}
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

Post by New(User) » Sun Feb 01, 2004 11:57 am

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

Post by New(User) » Sun Feb 01, 2004 1:47 pm

?

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Wed Feb 04, 2004 6:48 pm

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]

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

Re: 615 what's the tricky input

Post by horape » Sun Feb 08, 2004 5:11 am

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

Post by miras » Fri Mar 19, 2004 9:15 am

it is not a tree... becouse tere is loop.... ;)
MIras

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm

Post by paulidirac » Mon Jun 14, 2004 7:46 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?

Post Reply

Return to “Volume 6 (600-699)”