V našem algoritmu bude klíčové následující pozorování:
Tvrzení: Dvě zaklínadla jsou ekvivalentní právě tehdy, když čísla přiřazená každému z písmen a ... z tvoří stejnou posloupnost.
Než si toto tvrzení dokážeme, demonstrujme si jeho platnost na zaklínadlech ze zadání úlohy:
121314 111234 abraka krabaaPosloupnosti čísel přiřazených písmenům a, b, k a r jsou následující: 134, 2, 1 a 1. Podle tvrzení, které jsme zatím nedokázali, jsou proto obě zaklínadla ekvivalentní.
11213 12131 dabra badarČísla přiřazená písmenu a v prvním zaklínadle tvoří posloupnost 13, zatímco v druhém tvoří posloupnost 23. Zaklínadla tedy dle našeho tvrzení nejsou ekvivalentní.
Nyní si výše uvedené tvrzení dokážeme:
Důkaz: Pokud v zaklínadle vyměníme dvě sousední písmena, která nejsou v abecedě těsně vedle sebe, čísla přiřazená těmto písmenům se nezmění. Tedy v ekvivalentních zaklínadlech, musí být posloupnosti čísel přiřazených každému z písmen stejné.
Obrácenou implikaci, tj., že pokud čísla přiřazená každému z písmen a ... z tvoří stejnou posloupnost, pak jsou obě zaklínadla ekvivalentní, dokážeme indukcí dle délky zaklínadla. Tvrzení zřejmě platí pro jedno- a dvoupísmenná zaklínadla. Předpokládejme nyní, že obě zaklínadla jsou tvořena alespoň třemi písmeny. Zvolme v každém ze dvou zaklínadel písmena α a β, která mají přiřazeno největší číslo, a pokud je takových písmen více, tak ta, která jsou abecedně nejmenší. Protože, posloupnosti čísel přiřazených stejným písmenům jsou shodné v obou zaklínadlech, musí platit α=β.
Protože α je písmeno v prvním zaklínadle s největším číslem, nenásleduje za ním už žádné z písmen α^-, α a α^+, a lze ho tedy posloupností výměn přemístit na konec zaklínadla. Podobně můžeme na konec druhého zaklínadla přemístit písmeno β. Protože výměny dvou sousedních písmen, která nejsou v abecedě těsně vedle sebe, nemění čísla přiřazená jednotlivým písmenům, jsou posloupnosti čísel přiřazených jednotlivým písmenům v obou nových zaklínadlech shodné. Tato vlastnost zůstane zachována i po odebrání písmen α a β. Na takto získaná kratší zaklínadla, použijeme indukční předpoklad. Protože jsou zkrácená zaklínadla ekvivalentní, jsou ekvivalentní i zaklínadla s písmeny α a β na konci, a tedy i původní zaklínadla.
Právě dokázané tvrzení nám dává návod, jak otestovat, zda jsou dvě zaklínadla ekvivalentní. Nejdříve dle výše uvedených pravidel přiřadíme každému písmenu v zaklínadlech číslo, a pak zkontrolujeme, že posloupnosti čísel přiřazených stejným písmenům se shodují. Abychom se vyhnuli při této kontrole vícenásobnému průchodu zadanými zaklínadly, při přiřazování čísel si rovnou vytvoříme posloupnosti pro jednotlivá písmena. Navíc, abychom se vyhnuli (pomalé) dynamické alokaci paměti, v pomocném poli si budeme uchovávat odkazy na následující stejné písmeno v zadaném zaklínadle. Časová i paměťová složitost takovéhoto algoritmu je pro dvojici N-písmenných zaklínadel O(N+A), kde A je počet písmen, která se mohou v zaklínadlech vyskytovat (v našem případě A=26).
program zaklinadla;
const MAX=1000000;
var zaklinadla:array[1..2,1..MAX] of char; { zadaná zaklínadla }
delka:longint; { délka zaklínadel }
cisla:array[1..2,1..MAX] of longint; { čísla přiřazená jednotlivým písmenům v zaklínadlech }
prvni:array[1..2,'a'..'z'] of longint; { první výskyt daného písmena v zaklínadle (0=není tam) }
dalsi:array[1..2,1..MAX] of longint; { odkaz na další výskyt stejného písmena v zaklínadle }
vstup,vystup:text; { vstupní a výstupní soubory }
procedure nacti;
var i:longint;
c:char;
begin
for i:=1 to delka do
begin
read(vstup,zaklinadla[1][i],c,zaklinadla[2][i]);
readln(vstup);
end;
end;
procedure spocitej(z: integer);
var pozice:array['a'..'z'] of longint;
i:longint;
max:longint;
c:char;
begin
for c:='a' to 'z' do
begin
prvni[z][c]:=0;
pozice[c]:=0;
end;
for i:=1 to delka do
begin
max:=0;
if pozice[zaklinadla[z][i]]<>0 then
max:=cisla[z][pozice[zaklinadla[z][i]]];
if zaklinadla[z][i]<>'a' then
if pozice[pred(zaklinadla[z][i])]<>0 then
if cisla[z][pozice[pred(zaklinadla[z][i])]]>max then
max:=cisla[z][pozice[pred(zaklinadla[z][i])]];
if zaklinadla[z][i]<>'z' then
if pozice[succ(zaklinadla[z][i])]<>0 then
if cisla[z][pozice[succ(zaklinadla[z][i])]]>max then
max:=cisla[z][pozice[succ(zaklinadla[z][i])]];
cisla[z][i]:=max+1;
if pozice[zaklinadla[z][i]]=0 then
begin
prvni[z][zaklinadla[z][i]]:=i;
pozice[zaklinadla[z][i]]:=i;
end
else
begin
dalsi[z][pozice[zaklinadla[z][i]]]:=i;
pozice[zaklinadla[z][i]]:=i;
end;
dalsi[z][i]:=0;
end;
end;
function porovnej:boolean;
var c:char;
i1,i2:longint;
begin
spocitej(1);
spocitej(2);
for c:='a' to 'z' do
begin
i1:=prvni[1][c]; i2:=prvni[2][c];
while (i1<>0) and (i2<>0) do
begin
if cisla[1][i1]<>cisla[2][i2] then
begin
porovnej:=false; exit
end;
i1:=dalsi[1][i1];
i2:=dalsi[2][i2];
end;
if (i1<>0) or (i2<>0) then
begin
porovnej:=false; exit
end;
end;
porovnej:=true;
end;
begin
assign(vstup,'magie.in');
assign(vystup,'magie.out');
reset(vstup);
rewrite(vystup);
readln(vstup,delka);
while delka<>0 do
begin
nacti;
if not porovnej then write(vystup,'ne');
writeln(vystup,'ekvivalentni');
readln(vstup,delka);
end;
close(vstup);
close(vystup);
end.
Úlohu si nejdříve přeformulujeme do řeči teorie grafů: máme dán graf G a chceme zjistit, jak lze jeho hrany rozdělit do takových dvojic, že hrany ve dvojici mají společný vrchol. Úloha zřejmě nemá řešení, pokud je hran lichý počet. V ostatních případech ukážeme, jak nalézt hledané rozdělení hran na dvojice. Budeme prohledávat graf do hloubky a vždy před návratem z každého vrcholu (tedy poté, co byly zpracovány všechny sousední dosud neprojité vrcholy) provedeme následující: Vezmeme všechny dosud nespárované hrany sousedící s aktuálním vrcholem. Pokud je hran lichý počet, vynecháme hranu vedoucí k otci (ta musí být dosud nespárovaná). Nyní máme sudý počet hran a můžeme je tedy libovolně spárovat. Po spárování hran můžeme ukončit zpracování aktuálního vrcholu a vrátit se k otci. Tímto způsobem se nám muselo podařit spárovat všechny hrany, protože u každého vrcholu jsme nechali nespárovanou nejvýše hranu vedoucí k otci, ale ta byla nutně spárována při zpracovávání otce. Ani u posledního zpracovávaného vrcholu problém nastat nemohl (teoreticky by mohla nastat situace, že by nebylo kterou hranu vynechat, pokud by hran u tohoto vrcholu zbyl lichý počet) — hran byl celkem sudý počet, spárováním některých hran jsme mohli vyřídit pouze sudý počet hran, a tak nám u posledního vrcholu musel zbýt sudý počet hran, které snadno spárujeme. Algoritmus má časovou i paměťovou složitost O(M+N), kde N je počet vrcholů grafu G a M počet jeho hran.
program asfalter;
const
INP = 'asfalt.in';
OUT = 'asfalt.out';
MAXN = 10000;
MAXM = 40000;
type
{Mezi kterými vrcholy hrana vede a s kterou je spárována (-1 pokud dosud není)}
edge = record
a, b : Integer;
pair : Longint;
end;
{Počátek hran od daného vrcholu v seznamu hran a stupeň vrcholu}
vertex = record
start : Longint;
deg : Integer;
visited : Integer;
end;
var
et : Array[1..MAXM] of edge; {Pole se všemi hranami}
ep : Array[1..2*MAXM] of Longint; {Čísla hran seřazená podle vrcholů, ke kterým patří}
v : Array[1..MAXN] of vertex; {Pole s vrcholy}
vn, en : Longint; {Počet vrcholů a hran}
{Načti vstup a vytvoř reprezentaci grafu}
procedure read_input;
var
i : Longint;
FI, FO : Text;
begin
Assign(FI, INP);
Reset(FI);
Read(FI, vn, en);
{Otestujeme, jestli je úloha zjevně neřešitelná}
if en mod 2 = 1 then begin
Assign(FO, OUT);
Rewrite(FO);
WriteLn(FO, 'Cesty nelze vyasfaltovat.');
Close(FO);
Close(FI);
Halt;
end;
for i := 1 to vn do begin
v[i].deg := 0;
v[i].visited := 0;
end;
for i := 1 to en do begin
Read(FI, et[i].a, et[i].b);
et[i].pair := -1;
Inc(v[et[i].a].deg);
Inc(v[et[i].b].deg);
end;
Close(FI);
{Seřadíme si pole s hranami}
v[1].start := 1;
for i := 2 to vn do begin
v[i].start := v[i-1].start+v[i-1].deg;
v[i-1].deg := 0;
end;
v[vn].deg := 0;
for i := 1 to en do begin
ep[v[et[i].a].start+v[et[i].a].deg] := i;
Inc(v[et[i].a].deg);
ep[v[et[i].b].start+v[et[i].b].deg] := i;
Inc(v[et[i].b].deg);
end;
end;
{Vrátí druhý konec hrany}
function edge_end(v : Longint; edgenum : Longint) : Longint;
begin
if et[edgenum].a <> v then
edge_end := et[edgenum].a
else
edge_end := et[edgenum].b;
end;
{Vytiskne výsledek}
procedure print_out;
var
i : Longint;
O : Text;
v : Array[1..4] of Integer;
tmp : Integer;
begin
Assign(O, OUT);
Rewrite(O);
for i := 1 to en do begin
if et[i].pair > i then begin
v[1] := et[i].a;
v[2] := et[i].b;
v[3] := et[et[i].pair].a;
v[4] := et[et[i].pair].b;
if (v[1] = v[3]) or (v[1] = v[4]) then begin
tmp := v[1];
v[1] := v[2];
v[2] := tmp;
end;
if (v[4] = v[1]) or (v[4] = v[2]) then begin
tmp := v[3];
v[3] := v[4];
v[4] := tmp;
end;
WriteLn(O, v[1],' ', v[2],' ', v[4]);
end;
end;
Close(O);
end;
{Prohledávání do hloubky na párování hran}
procedure DFS(act, parent : Integer);
var
pair, i : Longint;
begin
pair := -1;
v[act].visited := 1;
{Zavoláme se na všechny sousední vrcholy, ve kterých jsme dosud nebyli}
for i := v[act].start to v[act].start+v[act].deg-1 do
if v[edge_end(act, ep[i])].visited = 0 then
DFS(edge_end(act, ep[i]), act);
{Nyní spárujeme zbylé hrany}
for i := v[act].start to v[act].start+v[act].deg-1 do
if (et[ep[i]].pair = -1) and (edge_end(act, ep[i]) <> parent) then begin
if pair = -1 then
pair := ep[i]
else begin
et[ep[i]].pair := pair;
et[pair].pair := ep[i];
pair := -1;
end;
end;
if pair <> -1 then begin {Hrana zbyla?}
{Spárujeme ji s hranou k rodiči}
i := v[act].start;
while edge_end(act, ep[i]) <> parent do
Inc(i);
et[ep[i]].pair := pair;
et[pair].pair := ep[i];
end;
end;
begin
read_input;
DFS(1, 1);
print_out;
end.