#!/usr/bin/perl -W

use strict;

my @node;

$node[0]= [ 1 , 4 , 7 ];
$node[1]= [ 0 , 2 , 9 ];
$node[2]= [ 1 , 3 , 6 ];
$node[3]= [ 2 , 4 , 8 ];
$node[4]= [ 0 , 3 , 5 ];
$node[5]= [ 4 , 6 , 9 ];
$node[6]= [ 2 , 5 , 7 ];
$node[7]= [ 0 , 6 , 8 ];
$node[8]= [ 3 , 7 , 9 ];
$node[9]= [ 1 , 5 , 8 ];
  
# Con m pasos, tenemos la suma de una progresión geométrica de razón (k - 1):
# n(k, m) = 1 + k + k(k-1) + k(k-1)^2 + ... + k(k-1)^(m-1)
# = 1 + k(1 + (k-1) + (k-1)^2 + ... + (k-1)^(m-1))
# = 1 + k*((k-1)^(m-1)*(k-1) - 1))/((k-1) - 1)
# = 1 + k((k-1)^m - 1)/(k - 2)

# En el caso de m = 2, que era el principal que estábamos tratando, si que
#   se puede para cualquier k.
  
my $k = 3;
# my $n = 10;
my $m = 2;
my ($r1,$r2,$ok,$kk,$iter);
my $n = 1 + $k*(($k-1)**$m - 1)/($k-2);



while (1){
    @node=();
    $kk=0;
    $iter=0;
    while ($kk<$n*$k/2){
	$ok=0;
	do{
	    $r1 = int rand ($n);
	    $r2 = int rand ($n);
	    next if ($r2 == $r1);
	    next if (scalar grep(/$r2/, @{$node[$r1]}) );
	    next if (scalar grep(/$r1/, @{$node[$r2]}) );
	    if ( !defined @{$node[$r1]}  && !defined @{$node[$r2]} ){
		push @{$node[$r1]}, $r2; 
		push @{$node[$r2]}, $r1;
		$kk++;
		$ok=1;
	    }elsif (!defined @{$node[$r1]} && scalar(@{$node[$r2]})<$k) {
		push @{$node[$r1]}, $r2;
		push @{$node[$r2]}, $r1;
		$kk++;
		$ok=1;
	    }elsif (!defined @{$node[$r2]} && scalar(@{$node[$r1]})<$k) {
		push @{$node[$r1]}, $r2;
		push @{$node[$r2]}, $r1;
		$kk++;
		$ok=1;
	    }elsif (scalar(@{$node[$r1]})<$k && scalar(@{$node[$r2]})<$k) {
		push @{$node[$r1]}, $r2;
		push @{$node[$r2]}, $r1;
		$kk++;
		$ok=1;
	    }
	    $iter++;
	}until ($ok==1 || $iter>$n*$n);
	last if $iter>$n*$n;
    }
    last if (comprobe()==1);
}


for my $i (0..$n-1){
    print "Node $i: ";
    for my $j (0..$k-1){
	if (defined $node[$i][$j]){
	    print "$node[$i][$j] ";
	}
    }
    print "\n";
}

exit 1;



sub comprobe {
    my $r;
    for my $i (0..$n-1){
	return -1 if (scalar @{$node[$i]} < $k);
	for my $j (0..$n-1){
	    $r = search ( $i, $j );
	    return -1  if ($r==-1);
	}
    }
    return 1;
}

sub search {
    my ($i, $j) = @_;
    my $r = -1;
    my $z;
    for my $p (0..$k-1){
	if (defined $node[$i][$p]){
	    $z = $node[$i][$p];
	    if ($z == $j){
		return 1;
	    }else{
		$r = search($i, $z);
		last if $r==1;
	    }
	}else { last; }
    }
    return $r;
}



__END__

elenamm2410@gmail.com

Se desea implantar un sistema de estaciones de emergencia. Los puestos de guardias van a
  interconectarse por una red de líneas telefónicas.
Cada estación debe estar en comunicación con cada una de las demás estaciones o bien
  directamente o bien por medio de una tercera estación.
Cada estación puede comunicarse directamente con a lo sumo tres de las estaciones restantes.
   ¿cuál es la mayor cantidad de estaciones que pueden interconectarse de esta manera? 


(Este problema puede interpretarse como un problema bidireccional, de cables, o de números
    de teléfono disponibles en cada nodo)

$nodo[0] = \(1,2,3); 
$nodo[1] = \(0,4,7);
$nodo[2] = \(0,4,7);
$nodo[3] = \(0,4,7);
$nodo[4] = \(0,5,6);
$nodo[5] = \(0,4,7);
$nodo[6] = \(0,4,7);
$nodo[7] = \(0,4,8);
$nodo[8] = \(0,4,7);