package Algorithm::Graph;
use strict;
use Util qw(unique); # dedupes an array

sub connected_components {
    my ($g) = @_;
    die "g must be arrayref" unless ref $g eq 'ARRAY';
    die "empty graph?" unless @$g>0;
    my $adj;
    foreach my $pair (@$g) {
        die "g must be arrayref of arrayrefs" unless ref $pair eq 'ARRAY';
        die "g must be arrayref of 2-elem arrayrefs" unless @$pair == 2;
        my ( $x, $y ) = @$pair;
        $adj->{$x}{$y} = 1;
        $adj->{$y}{$x} = 1;
    }
    my %comp;
    for my $node ( keys %$adj ) {
        next if $comp{$node};
        $comp{$node} = $node;
        my @neighbors = keys %{ $adj->{$node} };
        while ( my $n = pop@ neighbors ) {
            die "set diff?" if $comp{$n} && $comp{$n} ne $node;
            $comp{$n} = $node;
            push( @neighbors, grep {! exists($comp{$_})} keys %{ $adj->{$n} } );
        }
    }
    return [
        map {
            my $c = $_;
             [ sort grep { $comp{$_} eq $c } keys %comp ];
            } (sort (unique(values %comp)))
    ];
}

1;