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.
