title: Python: simple list merging based on intersections
body: <p>Consider there are some lists of integers as:</p>
  
  <pre><code>#--------------------------------------
  0 [0,1,3]
  1 [1,0,3,4,5,10,...]
  2 [2,8]
  3 [3,1,0,...]
  ...
  n []
  #--------------------------------------
  </code></pre>
  
  <p>The question is to merge lists having at least one common element. So the results only for the given part will be as follows:</p>
  
  <pre><code>#--------------------------------------
  0 [0,1,3,4,5,10,...]
  2 [2,8]
  #--------------------------------------
  </code></pre>
  
  <p><strong>What is the most efficient way to do this on large data (elements are just numbers)?</strong>
  Is <code>tree</code> structure something to think about?
  I do the job now by converting lists to <code>sets</code> and iterating for intersections, but it is slow! Furthermore I have a feeling that is so-elementary! In addition, the implementation lacks something (unknown) because some lists remain unmerged sometime! Having said that, if you were proposing self-implementation please be generous and provide a simple sample code [apparently <strong>Python</strong> is my favoriate :)] or pesudo-code.<br>
  <strong>Update 1:</strong>
  Here is the code I was using:</p>
  
  <pre><code>#--------------------------------------
  lsts = [[0,1,3],
          [1,0,3,4,5,10,11],
          [2,8],
          [3,1,0,16]];
  #--------------------------------------
  </code></pre>
  
  <p>The function is (<strong>buggy!!</strong>):</p>
  
  <pre><code>#--------------------------------------
  def merge(lsts):
      sts = [set(l) for l in lsts]
      i = 0
      while i &lt; len(sts):
          j = i+1
          while j &lt; len(sts):
              if len(sts[i].intersection(sts[j])) &gt; 0:
                  sts[i] = sts[i].union(sts[j])
                  sts.pop(j)
              else: j += 1                        #---corrected
          i += 1
      lst = [list(s) for s in sts]
      return lst
  #--------------------------------------
  </code></pre>
  
  <p>The result is:</p>
  
  <pre><code>#--------------------------------------
  &gt;&gt;&gt; merge(lsts)
  &gt;&gt;&gt; [0, 1, 3, 4, 5, 10, 11, 16], [8, 2]]
  #--------------------------------------
  </code></pre>
  
  <p><strong>Update 2:</strong>
  To my experience the code given by <strong>Niklas Baumstark</strong> below showed to be a bit faster for the simple cases. Not tested the method given by "Hooked" yet, since it is completely different approach (by the way it seems interesting).
  The testing procedure for all of these could be really hard or impossible to be ensured of the results. The real data set I will use is so large and complex, so it is impossible to trace any error just by repeating. That is I need to be 100% satisfied of the reliability of the method before pushing it in its place within a large code as a module. Simply for now <strong>Niklas</strong>'s method is faster and the answer for simple sets is correct of course.<br>
  <strong>However how can I be sure that it works well for real large data set?</strong> Since I will not be able to trace the errors visually!</p>
  
  <p><strong>Update 3:</strong>
  Note that reliability of the method is much more important than speed for this problem. I will be hopefully able to translate the Python code to Fortran for the maximum performance finally.</p>
  
  <p><strong>Update 4:</strong><br>
  There are many interesting points in this post and generously given answers, constructive comments. I would recommend reading all thoroughly. Please accept my appreciation for the development of the question, amazing answers and constructive comments and discussion.</p>