615 - Is It A Tree?

[broderic]

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

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]

hehe, i was being dumb. of course that's not a tree.
a simple one line fix and AC.

Thanks!
Broderick

[arc16]

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

[hank]

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]

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]

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

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.

[LeoST]

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

[New(User)]

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

?

[the LA-Z-BOy]

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

[horape]

?

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]

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

[paulidirac]

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?