looking for a set union find algorithm

Posted by Mig on Stack Overflow See other posts from Stack Overflow or by Mig
Published on 2010-06-18T06:05:33Z Indexed on 2010/06/18 6:13 UTC
Read the original article Hit count: 270

Filed under:
|
|

I have thousands of lines of 1 to 100 numbers, every line define a group of numbers and a relationship among them. I need to get the sets of related numbers.

Little Example: If I have this 7 lines of data

T1 T2
T3 
T4
T5
T6 T1
T5 T4
T3 T4

I need a not so slow algorith to know that the sets here are:

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5)
T3 T4 T5 (because T5 is with T4 in line 6 and T3 is with T4 in line 7)

but when you have very big sets is painfully slow to do a search of a T(x) in every big set, and do unions of sets... etc.

Do you have a hint to do this in a not so brute force manner?

I'm trying to do this in python.

Thanks

© Stack Overflow or respective owner

Related posts about python

Related posts about algorithm