I have solved the problem using DFS....just wanted to know why Union and Find fail....and yes Graph was directed so that might be the reason why it failed
On Mon, May 7, 2012 at 1:12 PM, vivek dhiman <[email protected]> wrote: > I will like to hear others opinions. > > But this was a pretty straight forward problem. As from the problem > statements: > "*You may assume that: * > > - *If there is an inheritance path from X to Y then there is no > inheritance path from Y to X.* > - *A class will never inherit from itself*." > > This implies that the graph was directed. > So to solve this you just do a BFS of the graph and as soon as you revisit > any already visited node for the first time, just stop BFS and say that > this has a diamond. which is nothing but a loop. > > Regards > Vivek Dhiman > > > On Mon, May 7, 2012 at 12:48 PM, Satyajit Bhadange < > [email protected]> wrote: > >> Considering the case : A inherits from B C D, >> B and C inherits from E. >> >> In this case Diamond is formed between A B C E. hence >=2 outdegree >> >> On Mon, May 7, 2012 at 12:41 PM, Manmeet Singh <[email protected]>wrote: >> >>> why more than 2, even 2 is ok >>> >>> On Mon, May 7, 2012 at 11:34 AM, Satyajit Bhadange < >>> [email protected]> wrote: >>> >>>> >>>> During the contest my first attempt for solving the problem was to find >>>> the class having more than tow out degrees. >>>> Starting from this class i apply union and find algorithm (which is use >>>> to detect cycle while constructing minimum spanning tree). >>>> >>>> This algorithm didnt work. I am still not getting why this would fail ? >>>> >>>> Can anyone please tell me why this would fail. >>>> >>>> Thanks & Regards, >>>> *Satyajit Bhadange >>>> Software Programmer* >>>> >>>> *Problems & Solutions* <http://www.satyajit-algorithms.com> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Google Code Jam" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/google-code?hl=en. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/google-code?hl=en. >>> >> >> >> >> -- >> >> Thanks & Regards, >> *Satyajit Bhadange >> Software Programmer* >> >> *Problems & Solutions* <http://www.satyajit-algorithms.com> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > Regards > Vivek Dhiman > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- Thanks & Regards, *Satyajit Bhadange Software Programmer* *Problems & Solutions* <http://www.satyajit-algorithms.com> -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
