Assuming everything fits in memory, the following seems reasonable. The basic idea is to essentially think of each set as a region in some abstract space. If two sets have an element in common, then they are directly connected in that space. Build a map of these direct connections, and then you can use a flood fill to find connected regions. Each connected region corresponds to an output set.

Here's a test implementation, assuming input is one line per input set with space separated values on each line. Output format is the same.

#!/usr/bin/env perl
use strict;

my @in;
my @out;
my %sawin;
my %merge;
my %merged;

while (<>)
{
chomp;
s/^\s+//;
push @in, [split /\s+/];
}

for (my $i = 0; $i < @in; ++$i) {
foreach (@{$in[$i]}) {
if (defined $sawin{$_}) {
$merge{$i}{$sawin{$_}} = 1;
$merge{$sawin{$_}}{$i} = 1;
} else {
$sawin{$_} = $i;
}
}
}

foreach (my $i = 0; $i < @in; ++$i) {
my %out;
next if $merged{$i};
$merged{$i} = 1;
$out{$_} = 1 foreach @{$in[$i]};
foreach my $ms (expand_merge($i)) {
$merged{$ms} = 1;
$out{$_} = 1 foreach @{$in[$ms]};
}
push @out, [sort {$a<=>$b} keys %out];
}

foreach (@out) {
print join(" ", @$_), "\n";
}

sub expand_merge
{
my($base) = @_;
my @todo = keys %{$merge{$base}};
my %done = ($base => 1);
while (@todo) {
my $next = shift @todo;
next if $done{$next};
$done{$next} = 1;
push @todo, keys %{$merge{$next}};
}
return keys %done;
}

Everything should be linear in the total number of elements except for expand_merge (the flood fill-like part). I think worst case for expand_merge could be quadratic in the number of elements, which would occur if each set overlapped a large fraction of the other sets.

If things won't fit in memory, I don't know how to do it in the general case. I suppose the first thing I'd do is look at the source of the sets to see if there are any limits on that. For instance, if we are dealing with a very large number of sets without a lot of members per set, and the range of numbers in each set is not very large, then it should be possible to partition the input into two sets of sets, A and B, such that it is easy to show that no sets in A contain any overlap with any sets in B, so we've reduced the problem to two smaller problems that can be solved independently and their outputs concatenated. Repeat.

For the general case, I'd start out by sorting the elements of each set, and by sorting the set of sets. While Googling for a refresher on external sorting and then coding up that part, I'd be hoping for some flash of brilliance to deal with what to do after that.

If no flash of brilliance arrived, I'd probably try something like this (assuming that I can at least fit several of the sets into memory at once). Let's assume that each set is stored in a file, named after its order in the sorted list of sets.

Read the first set into memory. Then scan through the remaining sets, in sorted order, checking each for overlap with the first. For any that overlap, merge them in memory with the first. When all the sets have been processed, or a point is reached where the first element of the current set is larger than the last element of the merged first set and so you can infer that no more merging will happen on this pass, write the merged first set out, replacing the original first set, and delete the files for all the sets that merged with the first.

Repeat this until no new sets merge with the first. At this point, you can mark the first as done, and it becomes the first output set.

Repeat with the first remaining set as your new first set, and so on.

As long as the biggest single output set and the biggest single input set will both fit in memory at the same time, I think that the above approach works.

I have a feeling that there is some clever way to do this that is much more efficient and is much more obvious (in the mathematical sense...in other words, after you look at it for a very long time and think about it really really hard it was clearly obvious).

My guess is that the clever solution will heavily involve sorting...not that I'm really going out on a limb with that guess, because almost everything is sorting when you look at it right. For example, here's a shell script that given a list of x, y coordinates on STDIN (one coordinate pair per line, x and y separated by space) outputs the result of doing one generation of Conway's Life with the input being the initial cell configuration:

> alive.$$
while read cells
do
echo $cells >> alive.$$
set x $cells
x=$2
y=$3
echo $x $((y-1))
echo $x $((y+1))
echo $((x-1)) $((y-1))
echo $((x-1)) $y
echo $((x-1)) $((y+1))
echo $((x+1)) $((y-1))
echo $((x+1)) $y
echo $((x+1)) $((y+1))
done | sort | uniq -c > neighbors.$$
grep '^ *3' < neighbors.$$ | sed -e 's/^ *[0-9].//'
grep '^ *2' < neighbors.$$ | sed -e 's/^ *[0-9].//' > has2.$$
sort alive.$$ -o alive.$$
comm -12 has2.$$ alive.$$
rm has2.$$ neighbors.$$ alive.$$

Note that the key operation is "sort". This runs in O(n log n) where n is the number of live cells (assuming your Unix uses an n log n sort...).