Buenas, ya he vuelto
Pues al final me he metido con el de grafos, me ha gustado mucho xD Y por cierto, decirte que me falto implementarle lo de varios casos por falta de tiempo, es decir, la entrada al programa es identica, solo que obvia el numero de casos y solo te resolvera el primero, si quieres probar otros casos hay que ejecutar de nuevo el programa (sorry, obviamente no presentaria eso asi en un concurso xDD)
Pero nada, queria que simplemente le echaras un vistazo a la parte principal del programa, el algoritmo y tal que es lo que importa al fin y al cabo, y ver que cambiarias tu o como lo harias (seguro que se puede hacer mas eficientemente que el mio
)
Aqui te lo dejo (Otra cosa, solo lo he hecho en pascal, en cuanto vuelva a tener un rato disponible intentare pasarlo a C a ver):
program circulos;
const
MAX = 20;
type
TValores = Record
Asignado : boolean;
Color : boolean; { 'True' = Verde; 'False' = Amarillo }
End;
TVertices = array [0..MAX] of TValores;
TCasos = array [1..MAX] of TVertices;
var
nCasos : integer;
nVertices : integer;
nAristas : integer;
inicio, fin : integer;
vertices : TVertices;
casos : TCasos;
flag : boolean;
i : integer;
procedure init_vertices (var c : TCasos);
var
i, j : integer;
begin
for i := 1 to MAX do
for j := 0 to MAX do
begin
c[i][j].Asignado := false;
c[i][j].Color := false;
end;
end;
function evalua (var v : TVertices; inicio, fin : integer) : boolean;
begin
if (v[inicio].Asignado = false) and (v[fin].Asignado = false) then { si ninguno ha sido asignado aun }
begin
v[inicio].Asignado := true;
v[inicio].Color := true;
v[fin].Asignado := true;
v[fin].Color := false;
evalua := true;
end
else
begin
if (v[inicio].Asignado) xor (v[fin].Asignado) then { si uno de los dos esta asignado }
begin
if v[fin].Asignado = false then
begin
v[fin].Asignado := true; { lo marcamos como coloreado }
v[fin].Color := not v[inicio].Color; { y le ponemos el color contrario al del otro vertice }
end
else
begin { en caso de que el que no estuviese coloreado aun fuera el vertice inicial, lo mismo para este }
v[inicio].Asignado := true;
v[inicio].Color := not v[fin].Color;
end;
evalua := true;
end
else
begin { si entramos aqui es porque ambos ya estan coloreados, comprobemos si es incompatible }
if v[inicio].Color = v[fin].Color then
evalua := false
else
evalua := true;
end;
end;
end;
{ -- MAIN --}
begin
init_vertices (casos);
flag := true;
readln (nCasos);
readln (nVertices, nAristas);
for i := 1 to nAristas do
begin
readln (inicio, fin);
flag := flag and (evalua (vertices, inicio, fin));
end;
if flag then
writeln ('Miguel, a pintar')
else
writeln ('No pierdas el tiempo');
end.
Ale, ahi lo tienes, dispara
Decirte tambien que voy a estar fuera hasta el viernes o asi, en cuanto vuelva a estar online le meto mano al susodicho problema nº 2, y tal vez traducir este a C
Gracias de nuevo por tus problemas, de verdad que son muy interesantes y me he entretenido mucho con ellos, sobre todo el ultimo claro (pa haber salido de un examen de GRAFOS hoy mismo y ponerme a hacer problemas de GRAFOS... xDD hay que echarle ganas)
Saludos!