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.

• Does the input consist only of pairs of positive integers divided by a dash? The line "a lone node with no connections would be considered an unconnected component." would suggest otherwise. Commented Oct 9, 2012 at 22:18
• @shiona Good point, I deleted that line. No lone nodes! Commented Oct 9, 2012 at 22:21
• Usually, these would be called connected components. Commented Oct 10, 2012 at 19:51

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


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:

Sage, 77

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


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;