Program Mosty; const MaxN=100; {maximální počet vrcholů} MaxM=10000; var Sousedi:array[1..MaxM] of 1..MaxN; {následnici vrcholů} V:array[1..MaxN+1] of 1..MaxM+1; {indexy určující, kde v Sousedi začínají následnici daného vrcholu} N,jedn,i,j:integer; {počet vrcholů, počet jednosměrek, čítač} Hladina,Spojeno:array[1..MaxN] of integer; {jako v kuchařce} {maximálni zjednosměrnění neorientovaného grafu} procedure Projdi(otec,x,NovaHladina:integer); var i:integer; begin Hladina[x]:=NovaHladina; {hladina nově nalezeného vrcholu} Spojeno[x]:=Hladina[x]; {zatím víme, že z něj vede spojení do} {něj samého, tj. do té samé hladiny} for i:=V[x] to V[x+1]-1 do {projdi všechny sousedy vrcholu V} if Hladina[Sousedi[i]] = -1 then begin {pokud sousední vrchol jestě neobjeven} Projdi(x,Sousedi[i], NovaHladina+1); {zkus z něj další pátrání} if Spojeno[Sousedi[i]] < Spojeno[x] then {našlo se spojení do nižší hladiny} Spojeno[x] := Spojeno[Sousedi[i]]; if Spojeno[Sousedi[i]] <= Hladina[x] then begin writeln('(',x,',',Sousedi[i],')'); {proto je toto DOPŘEDNÁ hrana} inc(jedn); end; end else {vrchol Sousedi[i] již byl při průchodu navštíven a není otec} if (Hladina[Sousedi[i]] < Spojeno[x]) and (Sousedi[i] <> otec) then begin Spojeno[x]:=Hladina[Sousedi[i]]; {ZPĚTNÁ hrana} writeln('(',x,',',Sousedi[i],')'); inc(jedn); end; end; begin readln(N); jedn:=0; V[1]:=1; j:=1; for i:=1 to N do begin while not eoln do begin {následnici vrcholu i} read(Sousedi[j]); inc(j); end; readln(); V[i+1]:=j; end; for i:=1 to N do Hladina[i]:=-1; for i:=1 to N do if Hladina[i] = -1 then Projdi(0,i,0); {pro vsechny komponenty grafu} writeln('Počet ulic k zjednosměrnění: ',jedn); end.