599  The Forrest for the Trees
Moderator: Board moderators

 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:
1. Read data
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
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:
1. Read data
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)
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?
I don't know if there are such trickies, but my AC program deals with them.
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

 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 nonintresting nodes [means: not in list] but WA too)
Best regards
DM
[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 nonintresting 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)
Born from ashes  restarting counter of problems (800+ solved problems)
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 39
 Joined: Fri Nov 14, 2003 11:18 pm
 Location: Riga, Latvia
 Contact:

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
599The 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=vcount 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
If the above method is correct can someone please help me debug the code?
Thank you.
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=vcount 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
If the above method is correct can someone please help me debug the code?
Thank you.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 599The forest for the trees
acorn not acron
Check input and AC output for thousands of problems on uDebug!
Re: 599The forest for the trees
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.brianfry713 wrote:acorn not acron

 New poster
 Posts: 15
 Joined: Wed Jul 23, 2014 12:57 am
Re: 599The forest for the trees
I'm having an issue with my code. It works for the sample input but I get RE when submitting
I was trying to some test input and
works fine but
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
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;
}
Code: Select all
1
(A,B)
(A,C)
...
(A,V)
****
A,B,C,...,Z
Code: Select all
1
(A,B)
(A,C)
...
(A,W)
****
A,B,C,...,Z