Legend wrote: > Suppose that I have some data: > > 12,30 > 12,45 > 2,3 > 7,8 > 3,9 > 30, 8 > 45,54 > 56,65 > > Where (a,b) indicates that a is connected to b. I want to get all > connected nodes to one point. For instance, the output of the above > example should be something like: > > Group 1 > 2,3 > 3,9 > Group 2 > 12,30 > 12,45 > 30,8 > 7,8 > Group 3 > 45,54 > Group 4 > 56,65 > > The order is not important as long as the whole group stays together. > Reason why they are grouped like that: > > 1. 2 is connected to 3 and 3 is connected to 9 and so we put all the > three, i.e. 2,3,9 into one group. > 2. 12 is connected to 45 and 12 is also connected to 30 so we put > these in the same group but 30 is connected to 8 and 8 is connected to > 7 so ultimately we put all these into the same group. > 3. 45 and 54 are connected but not related to any other numbers so we > put them into another group > 4. 56 and 65 are connected but not related to any other numbers so we > put them into another group > > I am unable to figure out an algorithm for this. Can someone guide me?
You can use disjoint data structures for this. A good tutorial can be found at http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
