599 - The Forrest for the Trees

[Dominik Michniewski]

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

[little joey]

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]

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

[little joey]

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]

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

[Aleksandrs Saveljevs]

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]

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

[L I M O N]

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:
1.Read Data.
2.for each unvisited node I check is there any cycle exits with it

[daveon]

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]

I don't understand what you mean.
A tree must not contain a cycle, right ?
So you mean the graph contains a cycle ?
Please give me test cases, because I'm still confused about the right answer.

[calicratis19]

deleted.

[piyukr]

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

If the above method is correct can someone please help me debug the code?
Thank you.

[brianfry713]

acorn not acron

[vsha041]

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]

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