5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – shiona Oct 9 '12 at 22:18
  • \$\begingroup\$ @shiona Good point, I deleted that line. No lone nodes! \$\endgroup\$ – arshajii Oct 9 '12 at 22:21
  • 3
    \$\begingroup\$ Usually, these would be called connected components. \$\endgroup\$ – Ilmari Karonen Oct 10 '12 at 19:51
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Sage, 77

len(Graph([t.split('-')for t in raw_input().split()]).connected_components())
\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.