Determine number of connected components

Question

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.

Answer 1

Ruby, 77 characters

gets;0while$_.sub!(/\b(\d+)\b(.*) (\1-\d+|\d+-\1)\b/,'\3\2');p$_.count(" ")+1

A first plain attempt in Ruby. It collects the sub-graphs using a regular expression until no more connections can be made.

Examples:

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

> 1-2 2-3 4-5
2

> 1-2 3-4 8-9 1-6 5-7 7-4 10-9
3

Answer 2

Mathematica 126

With x holding the input string,

t = ToExpression; 
Length@ConnectedComponents@Graph[Characters /@ ImportString[x, "Table"][[1]] /. 
{a_, "-", b_} :>   UndirectedEdge[t@a, t@b]]

---

If x is input instead as a list of undirected edges, in standard Mathematica format, the solution can be reduced to 34 chars:

Length@ConnectedComponents@Graph@i

Example:

Answer 3

Sage, 77

len(Graph([t.split('-')for t in raw_input().split()]).connected_components())

Answer 4

Golfscript, 67 62 characters

This can probably be golfed down a little more but...

" "/{"-"/{~}%}%0\{.}{(:^;{.{^&},.{+}*}{.@\-\{+}*:^;}while\)\}while;

'-'%{~}%2/0\{.}{(:^;{.{^&},.{+}*}{.@\-\{+}*:^;}while\)\}while;

Important note: this ONLY works on the ruby interpreter for golfscript (from golfscript.com), NOT on the online golfscript app, because the online app incorrectly handles nested while loops. Here's the commented code:

" "/{"-"/{~}%}% # parse into array of number pairs

'-'%{~}%2/        # parse into array of number pairs
0\                # push the counter under the current set
{.}               # copy top for the condition pop
{
    (:^;          # grab leftmost pair
  {
    .{^&},        # grab any matching the left pair, make a copy for the
    .{+}*         # condition, and merge the copy's elements together
  }{
    .@\-\         # remove the matches from remaining set
    {+}*:^;       # merge matches together & assign to '^'
  }while
  \)\             # update the counter underneath
}while;