title: Algorithm to partition graph into complete subgraphs
body: <p>I need an algorithm to partition the vertices of an undirected graph into one or more subgraphs, such that each subgraph is a complete graph (every vertex adjacent to every other vertex). Each vertex needs to be in exactly one of the subgraphs.</p>
  
  <p>Here's an example:</p>
  
  <pre class="lang-py prettyprint-override"><code>input = [
      (A, B),
      (B, C),
      (A, C),
      (B, D),
      (D, E),
  ]
  output = myalgo(input)  # [(A, B, C), (D, E)]
  </code></pre>
  
  <p>Here's an image that better describes the problem:</p>
  
  <p><a href="https://i.stack.imgur.com/eOV7J.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/eOV7J.png" alt="example"></a></p>
  
  <p>The input list is sorted in decreasing order by distance, that's why I connect A-B-C instead of B-D. </p>
  
  <p>I thought this might be called "strongly connected components", and have already tried the following solutions:</p>
  
  <ul>
  <li><p><a href="https://stackoverflow.com/questions/44594132/finding-a-strongly-connected-components-in-undirected-graphs">Finding a Strongly Connected Components in unDirected Graphs</a>: it's looking for something different</p></li>
  <li><p><a href="https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs">Finding all cycles in undirected graphs</a>: it gives me <em>many</em> cycles and not the best, it doesn't care about the input order.</p></li>
  <li><p><a href="https://stackoverflow.com/questions/35021792/an-algorithm-to-create-clusters-from-data-pairs-in-python/35021895">An algorithm to create clusters from data pairs in python</a>: it connects all the components, just because there is a path between them (A-B-C-D-E).</p></li>
  <li><p><a href="https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm" rel="nofollow noreferrer">Kosaraju's algorithm</a>: it works only with a directed graph.</p></li>
  </ul>