Hi Satyajit, I only glanced at this problem (slept through this round :-), but it seemed like the obvious solutions is to just run DFS, checking that we never encounter a vertex twice (if I understood the problem).
When you mention union-find, I am thinking of Kruskal's algorithm, but it's not immediately obvious how to apply that here. Roughly, we could put each vertex in its own singleton set. Then we could run a DFS (or BFS, if you like) starting at each root (in-degree zero). As we encounter each vertex, we could union it with its parent. But before we do this, we'd need to first check that it wasn't already unioned to its parent, which is essentially equivalent to checking whether it's been visited. So, yes, it seems like you could use union-find, but only in a sort of trivial way. Perhaps I'm missing something, though. Mike On Monday, May 7, 2012 2:47:22 AM UTC-5, Satyajit Bhadange wrote: > > 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 > <vivek4dhiman<[email protected]> > @xxx> 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 >> <satyajit.bhadange@<[email protected]> >> xxx> 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 >>> <mans.austin@<[email protected]> >>> xxx> wrote: >>> >>>> why more than 2, even 2 is ok >>>> >>>> On Mon, May 7, 2012 at 11:34 AM, Satyajit Bhadange >>>> <satyajit.bhadange@<[email protected]> >>>> xxx> 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 view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/CpOMIb9BSwkJ. 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.
