## 599 - The Forrest for the Trees

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 599 - The Forrest for the Trees

I think that it's easy problem , but I got several WA's when I try to solve it.
I use DFS to count trees and acorns, but I could miss something. Could anyone help me and post some test cases ?

My algorithm is:
2. for every unvisited node
2.1. if node has no edges -> it's acorn
2.2. else run DFS and increase number of trees if this is a tree (is tree if when I run DFS from node x I cannot reach node y such that x >= y)

Is my algorithm wrong ? Could anyone help me ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Dominik,
I think your algo is correct.
What is the output for the following testcase?

Code: Select all

``````1
(A,B)
(B,C)
(B,D)
(D,E)
(F,G)
****
A,B,C,E
``````
I don't know if there are such trickies, but my AC program deals with them.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
My program outputs:
[c]There are 1 tree(s) and 0 acorn(s).[/c]
I assumed, that if I don't get node name in list, I don't check it (but I don't eliminate edges from the tree). I try to send code, where I ignore edges, which are concatenated with non-intresting nodes [means: not in list] but WA too)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, my program gives 1 tree & 1 acorn. I can't think of any more special cases, apart from the no edges, no nodes and no nodes&edges cases...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I got Accepted on this problem.
I think, that input data contains incorrect test cases - graph with cycles and so on ...
My accepted solution counts this 'trees' and 'acorns'. But in my opinion is something wrong with this IO ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
The data set is OK, no illegal test cases.
You can mail me your old code, I'll tell you what was wrong.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Maybe I have a mistake on my code... I try to search 'backwards' in my codes and if I find incorrect program I send it to you

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
To Dominik,
Do you please explain me how did you get accepted?
It seems to me very easy, but I got WA several times.
My algorithm is:
2.for each unvisited node I check is there any cycle exits with it

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

I think the problem is in cycle detection. Try looking for cycle detection algorithms that use DFS and color nodes with WHITE,GREY,BLACK.

At least that was my mistake.
Cheers.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I don't understand what you mean.
A tree must not contain a cycle, right ?
So you mean the graph contains a cycle ?

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### why wa

deleted.
Heal The World

piyukr
New poster
Posts: 17
Joined: Sun Jan 26, 2014 10:35 am

### 599-The forest for the trees

here is the problem statement:http://uva.onlinejudge.org/index.php?op ... roblem=540

Can I solve it in this manner?
First count the no. of vertices and edges in the graph.
Then using a bitset of size 26 , mark the vertices which has at least one edge.let it be count(say).
In a graph with no cycles,
no. of connected components=no. of vertices - no. of edges
Therefore ,
no of acorns=v-count and
no of trees= no of connected components - no of acorns.

Is this method a correct way to solve this problem?

I tried it on various test inputs and found it to be working well . However, my code for this got WA . code :http://ideone.com/jHvdzn

Thank you.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 599-The forest for the trees

acorn not acron
Check input and AC output for thousands of problems on uDebug!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 599-The forest for the trees

brianfry713 wrote:acorn not acron
That was nice ! Attention to detail ! Sometimes I use windiff to compare sample output with my output just to catch these kind of "eye tricking" errors.

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

### Re: 599-The forest for the trees

I'm having an issue with my code. It works for the sample input but I get RE when submitting

Code: Select all

``````#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

typedef vector<int> vi;

class UnionFind{
private:
vi p,rank;
int singles, sets;
public:
UnionFind(int N){
singles=sets=N;
rank.assign(N,0);
p.assign(N,0);
for(int i=0;i<N;i++)
p[i]=i;
}
int findSet(int i){
return (p[i]==i) ? i : (p[i]=findSet(p[i]));
}
bool isSameSet(int i,int j){
return findSet(i)==findSet(j);
}
void unionSet(int i,int j){
if(!isSameSet(i,j)){
int x=findSet(i), y=findSet(j);
sets--;
if(rank[x]==0)
singles--;
if(rank[y]==0)
singles--;
if(rank[x]>rank[y])
p[y]=x;
else{
p[x]=y;
if(rank[x]==rank[y]) rank[y]++;
}
}
}
int getSingles(){
return singles;
}
int getSets(){
return sets;
}
};

int main(){
int TC, E, V, trees, acorns;
char from[26],to[26],t;
map<char,int> m;
scanf("%d",&TC);
while(TC--){
E=0;
m.clear();
//scan in edges
while(scanf(" (%c,%c)",&from[E],&to[E])==2)
E++;
//scan in vertices
V=0;
scanf("%s");
scanf(" %c",&t);
m[t]=V;
V++;
while(scanf(",%c",&t)==1){
m[t]=V;
V++;
}
//UFDS
UnionFind* U=new UnionFind(V);
for(int i=0;i<E;i++)
U->unionSet(m[from[i]],m[to[i]]);
acorns=U->getSingles();
trees=(U->getSets())-acorns;
printf("There are %d tree(s)  and %d acorn(s).\n",trees,acorns);
}
return 0;
}
``````
I was trying to some test input and

Code: Select all

``````1
(A,B)
(A,C)
...
(A,V)
****
A,B,C,...,Z
``````
works fine but

Code: Select all

``````1
(A,B)
(A,C)
...
(A,W)
****
A,B,C,...,Z
``````
Gives me a very wierd error where the TC variable is somehow reset to 42 and it gives me 42 results with all but the first being 0 trees, 1 acorn