599 - The Forrest for the Trees

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 599-The forest for the trees

Post by lbv » Mon Jul 28, 2014 9:58 pm

apcastelein wrote:I'm having an issue with my code. It works for the sample input but I get RE when submitting
Try configuring your compiler to show you all possible warnings, as that may help you catch subtle bugs. For example, when I compiled your code, I received:

Code: Select all

p.cpp: In function ‘int main()’:
p.cpp:64:17: warning: format ‘%s’ expects a matching ‘char*’ argument [-Wformat=]
       scanf("%s");
                 ^
If you want to skip that string in scanf (not store it anywhere), you may use the assignment-suppression character (see scanf's documentation for details). For example:

Code: Select all

       scanf("%*s");
Notice that there is also one space too many between "tree(s)" and "and".

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

Re: 599-The forest for the trees

Post by apcastelein » Tue Jul 29, 2014 7:03 pm

Thank you very much. I got it accepted now.

uohzxela
New poster
Posts: 4
Joined: Thu Jan 01, 2015 2:51 pm

Re: 599 - The Forrest for the Trees

Post by uohzxela » Fri Jan 09, 2015 5:26 am

Just got AC for the problem.

Turns out you don't need to implement cycle-finding for your DFS (DFS with cycle-finding will give WA). Just a simple DFS with coloring will do; a tree will contain colored nodes. Any white node in adjacency list with an empty list is an acorn. Be sure to add edge twice because the graph is undirected.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 599 - The Forrest for the Trees

Post by uDebug » Tue Apr 21, 2015 11:54 am

Added some input to help with testing / debugging here:

http://www.udebug.com/UVa/599
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 5 (500-599)”