Determine number of connected components You are given a graph represented through an adjacency list. For example, the input

1-2 2-3 3-4 4-1


would correspond to the graph with nodes 1, 2, 3 and 4, where 1 is connected to 2, 2 is connected to 3, 3 is connected to 4, and 4 is connected to 1 (forming a square).

The task is to determine the number of of connected components of the graph represented by an inputted adjacency list. A "connected component" is a set of nodes from which there is no path to any other node that is not in the set.

Example:


  Intput: 1-2 2-3 4-5
  Output: 2




Language of your choice - shortest code possible.
Ruby, 77 characters
gets;0while$_.sub!(/\b(\d+)\b(.*) (\1-\d+|\d+-\1)\b/,'\3\2');p$_.count(&quot; &quot;)+1

A first plain attempt in Ruby. It collects the sub-graphs using a regular expression until no more connections can be made.
Examples:
&gt; 1-2 2-3 3-4 4-1
1

&gt; 1-2 2-3 4-5
2

&gt; 1-2 3-4 8-9 1-6 5-7 7-4 10-9
3