gistfile1.py

def f(list_of_lists):
    sets = {}
    for lst in list_of_lists:
        s = set(lst)
        for x in set(lst):
            if x in sets:
                t = sets[x]
                for y in t:
                    sets[y] = s
                s.update(t)
            else:
                sets[x] = s
    ids = set()
    result = []
    for s in sets.itervalues():
        if id(s) not in ids:
            ids.add(id(s))
            result.append(s)
    return result

def merge(lsts):
  sets = [set(lst) for lst in lsts if lst]
  merged = 1
  while merged:
    merged = 0
    results = []
    while sets:
      common, rest = sets[0], sets[1:]
      sets = []
      for x in rest:
        if x.isdisjoint(common):
          sets.append(x)
        else:
          merged = 1
          common |= x
      results.append(common)
    sets = results
  return sets

a = [[804, 7648, 3687, 5256, 765, 4269, 3644, 4471, 2216, 9118],
     [914, 1882, 3009, 7115, 3598, 9998, 6970, 9467, 3085, 2152],
     [8649, 9773, 6778, 563, 1904, 4123, 9541, 7587, 1996, 9053],
     [3031, 2720, 3884, 6102, 4506, 4420, 1240, 5816, 3263, 9726],
     [1457, 4872, 7666, 4124, 9768, 9777, 8006, 972, 4300, 38],
     [5250, 4749, 3753, 7243, 7543, 3017, 1917, 6245, 685, 9395],
     [7901, 7002, 8414, 3737, 5189, 9562, 3853, 5425, 4001, 5558],
     [5812, 4465, 1072, 6820, 884, 5808, 1798, 4394, 2357, 8208],
     [3176, 1740, 5244, 1652, 3746, 3609, 6403, 5753, 7441, 4210],
     [5907, 9621, 1292, 416, 1915, 9495, 9016, 148, 8691, 8407],
     [7532, 8093, 3029, 8126, 5667, 3882, 1159, 7034, 3214, 6807],
     [2579, 4018, 601, 2976, 1319, 7120, 7748, 2431, 8866, 4660],
     [5850, 3021, 2647, 5619, 8439, 4026, 1187, 4852, 3597, 9487],
     [8544, 6243, 482, 6615, 8517, 6523, 3311, 7179, 2086, 8241],
     [4662, 3096, 6813, 3202, 4792, 5657, 3706, 1648, 6059, 6000],
     [2566, 5464, 3643, 2842, 6279, 7812, 344, 736, 7346, 239],
     [2690, 5580, 2212, 8434, 6389, 8981, 6436, 2662, 5244, 864],
     [4776, 4723, 4590, 7438, 6263, 5149, 4013, 4946, 4538, 9173],
     [8000, 4334, 6243, 7190, 1769, 5238, 758, 7222, 6473, 4876],
     [3244, 5268, 7099, 3850, 3885, 144, 3948, 4081, 8078, 4515],
     [4360, 6738, 3930, 4448, 9403, 3435, 5969, 7379, 7230, 7410],
     [9492, 4764, 9173, 6234, 369, 6229, 4641, 5123, 8986, 2979],
     [6138, 9009, 927, 7754, 1765, 9203, 8045, 1799, 8082, 3996],
     [3350, 2126, 7166, 6156, 6157, 6942, 4403, 30, 1478, 605],
     [9996, 9251, 9708, 5074, 3639, 8702, 7362, 6426, 9807, 3857],
     [9069, 3326, 1456, 7389, 3656, 9009, 46, 236, 3641, 5870],
     [3023, 3210, 8634, 2513, 2871, 1582, 7222, 1175, 9089, 1477],
     [8664, 5088, 501, 7022, 3604, 2899, 8456, 2508, 3842, 5755],
     [2353, 6971, 8400, 8755, 9276, 4054, 8720, 8256, 8833, 6183],
     [4472, 3494, 5285, 8254, 7790, 7703, 5464, 4510, 3450, 4607],
     [2260, 7011, 8627, 4918, 9037, 5397, 2394, 3881, 6868, 8533],
     [4421, 8858, 7477, 4471, 3029, 6298, 5479, 850, 835, 4592],
     [2272, 815, 3872, 3719, 5250, 6983, 6256, 2042, 753, 7433],
     [5128, 8870, 2982, 464, 5201, 3124, 2983, 7755, 7004, 7594],
     [3054, 1715, 3523, 7672, 7935, 5332, 7044, 1097, 7935, 2942],
     [6519, 2766, 2012, 2322, 9579, 4311, 3193, 4418, 7764, 3129],
     [9108, 7841, 1654, 890, 7097, 961, 7665, 6905, 6220, 1707],
     [5805, 7377, 5458, 5423, 4100, 2521, 9748, 4761, 216, 4496],
     [7952, 9854, 140, 9845, 2600, 8274, 4668, 3549, 619, 7546],
     [5136, 8150, 2083, 2729, 3345, 8835, 894, 1525, 9433, 1412],
     [7514, 5356, 8953, 6612, 5730, 936, 1827, 4920, 4872, 200],
     [8266, 4427, 3476, 2934, 288, 300, 6589, 8600, 4927, 6306],
     [5086, 6083, 6122, 5085, 2678, 1157, 4621, 3107, 3224, 105],
     [4229, 6061, 9047, 2492, 7168, 7273, 126, 8295, 9607, 5756],
     [4215, 7269, 8444, 5338, 5571, 1687, 1534, 7066, 6455, 1022],
     [5151, 3379, 2492, 6068, 7549, 8251, 3963, 3244, 8556, 9773],
     [2391, 2877, 4200, 7573, 1536, 9618, 5532, 7608, 1094, 2913],
     [1801, 2128, 5960, 167, 4631, 9727, 7102, 292, 3289, 587],
     [6915, 9233, 7803, 627, 7465, 1804, 2861, 9239, 31, 3276],
     [8559, 3109, 9188, 3594, 3169, 5192, 7574, 9436, 3328, 7140],
     [7502, 7331, 2674, 995, 6827, 8073, 931, 178, 2035, 2533],
     [5872, 4096, 411, 4028, 9437, 4011, 262, 6797, 39, 5794],
     [7632, 6334, 6004, 4491, 1400, 7983, 8803, 4584, 2425, 2145],
     [3825, 59, 5151, 5150, 8761, 4312, 19, 3419, 1230, 5056],
     [2699, 8892, 5793, 3479, 8919, 9222, 6538, 8841, 1894, 9852],
     [6634, 4154, 320, 5642, 9883, 7698, 920, 9246, 7785, 3723],
     [4477, 630, 4059, 1732, 2717, 1680, 9690, 4229, 6249, 9178],
     [6767, 9446, 5668, 4860, 2167, 9617, 7130, 7567, 9450, 51],
     [6775, 288, 4092, 8435, 2247, 1730, 5230, 4371, 9640, 9215],
     [7537, 8369, 1484, 1900, 8920, 1302, 5877, 346, 3326, 6751],
     [2382, 3624, 2035, 7279, 3792, 8917, 3612, 5905, 9103, 2601],
     [6809, 5243, 418, 9578, 1962, 7588, 3516, 6352, 770, 7776],
     [1890, 6498, 5316, 7219, 7889, 7497, 603, 3549, 6503, 2867],
     [3190, 9066, 631, 7738, 2563, 9716, 1872, 7758, 6000, 4879],
     [8478, 2480, 159, 9395, 5961, 4943, 3637, 5719, 4947, 9283],
     [7994, 3541, 6970, 6835, 2296, 2660, 513, 7794, 9880, 4481],
     [9563, 1608, 4052, 9745, 2333, 1225, 5168, 9182, 4991, 1346],
     [4017, 2692, 659, 5368, 6119, 4835, 8572, 9250, 5088, 5114],
     [7342, 7279, 6890, 3496, 4039, 3251, 399, 4669, 9974, 5187],
     [1123, 7134, 2437, 7017, 8517, 3034, 7509, 5245, 5824, 3314],
     [4859, 582, 9282, 4366, 6865, 8303, 6015, 1998, 5962, 2717],
     [6463, 8473, 1114, 1177, 4906, 2383, 9503, 9878, 1512, 6420],
     [6017, 8921, 7211, 4299, 4150, 7250, 4212, 7681, 470, 2097],
     [5872, 5023, 7689, 362, 9161, 9165, 6845, 1959, 8349, 13],
     [4944, 260, 8277, 7021, 6641, 4296, 4966, 1934, 2088, 1097],
     [6953, 1685, 8716, 2509, 5397, 9526, 8515, 940, 7742, 180],
     [3310, 4671, 7605, 3237, 5205, 3701, 1777, 7363, 5969, 1494],
     [9372, 6326, 4939, 7889, 5761, 6906, 4945, 2751, 3515, 4920],
     [5153, 7696, 4036, 8789, 4582, 5662, 5183, 5247, 6237, 1730],
     [4033, 9800, 8869, 4215, 8974, 419, 9141, 9481, 419, 4454],
     [1260, 2071, 8878, 3001, 9391, 5308, 89, 7247, 6643, 8168],
     [7631, 4439, 4324, 9633, 5395, 992, 6820, 7534, 7666, 3815],
     [8162, 5111, 8263, 2381, 3088, 4244, 6100, 9912, 2336, 3294],
     [775, 3553, 5454, 9123, 6448, 2201, 9184, 4532, 3812, 3137],
     [5430, 6450, 984, 4697, 9866, 1690, 1861, 9622, 2371, 4891],
     [9787, 8428, 8055, 3800, 942, 6727, 6705, 7110, 4967, 4505],
     [6578, 2968, 1411, 913, 8433, 485, 9742, 1469, 7206, 9674],
     [5897, 9722, 6546, 4240, 5783, 7831, 2623, 401, 2795, 4808],
     [4431, 4155, 296, 8851, 3820, 1330, 5533, 8362, 8087, 8700],
     [3607, 5720, 6039, 9345, 7018, 2842, 1693, 363, 9315, 7841],
     [608, 5985, 1001, 3949, 3558, 3083, 6690, 8779, 3102, 7957],
     [8407, 5896, 3817, 2834, 7750, 9139, 6712, 6657, 5167, 2403],
     [1670, 5843, 9203, 137, 9111, 602, 9620, 2789, 9549, 3666],
     [4192, 7812, 3677, 9007, 37, 2179, 8400, 5517, 3005, 9588],
     [6735, 6577, 2672, 5862, 4627, 8451, 291, 1926, 2998, 5568],
     [5839, 3962, 6324, 5940, 8373, 1991, 3358, 4067, 6035, 6672],
     [3157, 3640, 9062, 238, 8116, 4934, 8245, 9065, 5690, 2177],
     [66, 987, 4262, 210, 5383, 4038, 5963, 5014, 5344, 3884],
     [1677, 5896, 5458, 5373, 2687, 9887, 7626, 8768, 5997, 7291],
     [346, 8636, 2517, 6162, 4927, 7352, 6795, 2608, 8920, 5952],
     [8260, 505, 8014, 6411, 6954, 8578, 5672, 4027, 2560, 2219],
     [2392, 327, 4060, 9626, 4869, 3006, 8585, 6810, 1745, 1259],
     [2205, 8668, 1940, 3832, 2950, 3881, 9831, 6093, 6988, 111],
     [3571, 4279, 9080, 6529, 7387, 4035, 7542, 405, 3114, 5571],
     [1828, 6004, 5085, 546, 8119, 1348, 6247, 4179, 1113, 7370],
     [6363, 7289, 6767, 2048, 9306, 5364, 161, 3389, 6241, 8154],
     [9060, 3911, 3403, 6767, 2611, 5499, 2108, 8546, 1463, 1158],
     [5496, 5296, 6187, 6965, 8899, 2818, 5124, 5997, 7677, 6837],
     [3286, 8929, 1967, 1132, 6920, 6387, 7791, 4348, 8511, 3340],
     [5979, 8124, 9675, 9128, 761, 7677, 1480, 1862, 6082, 6243],
     [5904, 5923, 3060, 5407, 8185, 2158, 8714, 4456, 5798, 4961],
     [4880, 2037, 6290, 105, 6856, 4071, 39, 690, 6884, 30],
     [9052, 7096, 422, 1132, 7816, 1300, 1761, 2393, 3054, 867],
     [2020, 3325, 3796, 2491, 2051, 838, 3952, 9701, 4395, 6076],
     [7224, 4359, 8364, 5757, 6645, 6422, 1088, 1809, 5328, 3584],
     [8152, 3384, 924, 4171, 3156, 5891, 2352, 4549, 7657, 8730],
     [8856, 746, 2918, 539, 6413, 3588, 3033, 5946, 2568, 9839],
     [7943, 1466, 7684, 4104, 4309, 2222, 7403, 4774, 2403, 6274],
     [1526, 5616, 5154, 9396, 7360, 5903, 2953, 9583, 6119, 4536],
     [9822, 6750, 6075, 9075, 2043, 9939, 1032, 8183, 4487, 6579],
     [7391, 9692, 7460, 3271, 9530, 7597, 9952, 1936, 4306, 6530],
     [8259, 7812, 1355, 1313, 5478, 1669, 3104, 2683, 9849, 7400],
     [3668, 2482, 4786, 421, 2804, 8074, 1340, 3094, 7937, 5756],
     [6266, 973, 2497, 1876, 3430, 7332, 6114, 8488, 9755, 1937],
     [8605, 5696, 3060, 6599, 6798, 6683, 918, 285, 9788, 4586],
     [7335, 142, 6868, 2646, 311, 5830, 3269, 7950, 9663, 6394],
     [3001, 6930, 1782, 4219, 3840, 4512, 3789, 6043, 6911, 9650],
     [7293, 1041, 5778, 6481, 5066, 5723, 3818, 1213, 4039, 7363],
     [2284, 4311, 3183, 4288, 3551, 5910, 9075, 635, 6974, 4005],
     [8195, 7051, 4106, 2361, 6444, 7984, 8377, 3862, 9119, 4189],
     [3490, 3334, 730, 13, 8883, 5131, 7399, 6691, 5653, 9543],
     [165, 8028, 84, 2300, 247, 1640, 7079, 9488, 4527, 4361],
     [9121, 9765, 6614, 780, 3122, 3458, 1862, 7058, 1358, 748],
     [5550, 1999, 2082, 4564, 8930, 8655, 2224, 534, 8427, 7393],
     [5102, 665, 902, 171, 6807, 4272, 1865, 6214, 4526, 1415],
     [791, 3699, 5706, 3218, 4622, 4173, 9031, 7460, 7793, 5302],
     [8203, 7673, 1921, 1179, 7978, 7225, 4425, 5935, 529, 2384],
     [3231, 1103, 9179, 8143, 9976, 4404, 9442, 5017, 6012, 2444],
     [6996, 7768, 4874, 1088, 6548, 5167, 8983, 9352, 1767, 7961],
     [5332, 777, 8586, 1721, 7800, 9044, 2634, 8632, 4282, 6525],
     [8926, 4990, 4754, 1292, 7436, 6726, 7187, 4163, 9746, 8860],
     [589, 5441, 1327, 5115, 7751, 7288, 7165, 3850, 6522, 4365],
     [9341, 8532, 9665, 4302, 9372, 6513, 6865, 9839, 1833, 9149],
     [9342, 506, 1823, 6352, 3123, 799, 7766, 3545, 5953, 5045],
     [1396, 1640, 1124, 2816, 1157, 7768, 2994, 4151, 1160, 6725],
     [7464, 5431, 1130, 8515, 1403, 7254, 3369, 8836, 6363, 8964],
     [1739, 380, 4001, 47, 95, 3327, 2077, 8794, 1122, 6912],
     [81, 5083, 4165, 9127, 16, 9620, 6976, 4383, 6129, 372],
     [6639, 5975, 6852, 5452, 8182, 7045, 5966, 3450, 6349, 3524],
     [2164, 5419, 6638, 9798, 839, 6082, 7384, 4562, 7128, 1133],
     [6983, 3629, 6464, 7335, 530, 2052, 8224, 9145, 3314, 135],
     [203, 9582, 8661, 8553, 4498, 8065, 8378, 4029, 5870, 3959],
     [5418, 8901, 5616, 4539, 2164, 413, 3942, 6190, 324, 8735],
     [2583, 5113, 3396, 2025, 6836, 3107, 1414, 367, 8079, 2660],
     [3863, 332, 8619, 3447, 8123, 8028, 7641, 6507, 6549, 2738],
     [5004, 9169, 2267, 177, 2221, 6024, 5101, 6490, 1784, 8229],
     [4519, 8133, 234, 1121, 5497, 1837, 2998, 6006, 5481, 2985],
     [8081, 5943, 793, 642, 8171, 2298, 4975, 4154, 8152, 6168],
     [5642, 2133, 942, 7955, 9233, 8260, 4346, 1677, 852, 6433],
     [1027, 3068, 2297, 1200, 8763, 4847, 1366, 7990, 5846, 4066],
     [2311, 7049, 8956, 7497, 4471, 9909, 3500, 7708, 7238, 6827],
     [4742, 3734, 5252, 7989, 936, 8201, 5533, 4286, 2171, 1840],
     [4043, 7899, 8090, 3201, 8361, 883, 3860, 2392, 7928, 851],
     [8070, 965, 2029, 3930, 8434, 9861, 5604, 7162, 6755, 8798],
     [2075, 237, 9062, 8249, 1015, 3800, 5863, 4287, 4023, 1175],
     [6729, 9695, 5542, 744, 6009, 3112, 3207, 127, 1079, 5459],
     [8348, 2051, 9233, 720, 5892, 4338, 9334, 681, 6364, 1902],
     [165, 5273, 4444, 1225, 403, 5691, 2220, 3667, 1172, 4334],
     [1467, 397, 3774, 6148, 3150, 614, 289, 4317, 1189, 2777],
     [514, 8400, 6736, 9861, 9025, 2675, 3985, 9664, 7588, 3991],
     [445, 1859, 1861, 4578, 6281, 9567, 5459, 2590, 1005, 9288],
     [8599, 7369, 8657, 1613, 2240, 2006, 7452, 7774, 2855, 6994],
     [2641, 2104, 1135, 8736, 8911, 6325, 7016, 9532, 4323, 6511],
     [3660, 9950, 2006, 5568, 3636, 8877, 2310, 2855, 4454, 8527],
     [3630, 3768, 400, 8385, 1794, 7288, 2476, 1648, 4686, 5665],
     [1204, 6900, 3340, 5711, 3074, 3475, 8657, 620, 255, 9716],
     [6224, 3479, 5339, 6677, 8789, 8804, 2231, 5828, 162, 1871],
     [6782, 4978, 3856, 3879, 2103, 995, 3398, 3618, 1483, 9390],
     [8353, 6704, 7590, 9963, 4256, 9966, 172, 383, 2819, 7290],
     [2988, 7169, 5274, 8959, 965, 5360, 5763, 9586, 5254, 8998],
     [5851, 9189, 6474, 1259, 6010, 9284, 5283, 6290, 6376, 9274],
     [8774, 3676, 3898, 5811, 2508, 2763, 695, 7804, 9780, 2747],
     [1295, 1766, 4771, 8394, 3967, 5238, 4715, 9139, 6832, 2718],
     [6272, 777, 30, 2376, 7035, 5143, 551, 691, 6124, 9990],
     [2043, 3720, 4202, 6975, 872, 3616, 6523, 1367, 70, 6734],
     [9064, 6038, 1690, 3952, 3387, 4229, 2998, 5961, 3086, 5116],
     [5128, 7616, 9694, 679, 1739, 3855, 7922, 5116, 3975, 4422],
     [6609, 3145, 9899, 2314, 8540, 3220, 2449, 2441, 9614, 692],
     [6847, 4351, 7956, 242, 8797, 5850, 9570, 6145, 7335, 7250],
     [5614, 673, 9504, 902, 5086, 6677, 2868, 9651, 2791, 7561],
     [7343, 6031, 985, 2301, 4867, 2024, 3532, 7430, 8907, 4074],
     [6478, 9175, 5896, 9832, 320, 3358, 768, 969, 494, 259],
     [8152, 1646, 5638, 1731, 9114, 822, 4726, 7278, 6220, 4054],
     [8464, 768, 9352, 9741, 6787, 4011, 886, 9412, 304, 7849],
     [3034, 4873, 4759, 83, 3382, 5756, 660, 2811, 7193, 9569],
     [340, 8496, 5301, 1627, 4682, 8945, 8239, 1226, 2841, 3504],
     [402, 743, 460, 4957, 6210, 8325, 157, 972, 477, 4676],
     [6140, 2849, 3396, 1187, 4118, 9860, 7614, 7916, 2625, 246],
     [531, 9890, 5304, 8768, 6254, 7635, 1276, 8228, 9064, 9799],
     [1249, 7612, 2487, 7334, 5925, 6483, 7345, 4025, 5017, 7483]]

import timeit

print timeit.timeit("f(a)", "from __main__ import f, a", number=1000)
print timeit.timeit("merge(a)", "from __main__ import merge, a", number=1000)