You could use the Graph module for this task. Completely untested:

use Graph;
...

sub process_one_line {
  my @relations = split /\s+/, shift;
  my $g = Graph::Undirected->new;

  for (@relations) {
    my ($x, $y) = split /_/;
    $g->add_edge($x, $y);
  }

  my @cc = $g->connected_components();

  my $num_clusters = int @cc;

  my @cluster_sizes = map { int @$_ } @cc;

  return +{ num => $num_clusters, sizes => \@cluster_sizes };
}

...
[download]