Algo: 1. Maintain a separate array class[] to indicate which element(a,b) belong to which class 2. assign first(a,b) to class 1. in eg: 12,30 to class 1 3. for each other element from then compare with members of existing class if yes assign this element with same class, else assign different class number.
hope this helps... it has worst case of complexity of O(n^2)... any better soln is appreciated. On 10/14/07, Vijay Chidambaram <[EMAIL PROTECTED]> wrote: > > > > 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 > . > > > > > -- ----------------------------------------------------------------------------------------------- Great people lived on one basic IDEA! "Thinking on their own lines." http://students.iiit.ac.in/~koushik_c/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" 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/algogeeks -~----------~----~----~----~------~----~------~--~---
