Anonymous     Pascal/Delphi     26 Feb 2012    
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
type
PTEdge = ^TEdge;
TEdge = record //тип описывает одно ребро
b, e :Integer; //начало и конец ребра
next :PTEdge; //т.к. все рёбра мы будем хранить в виде списка, то next - описывает следующее реброс в списке
end;
PTVertex = ^TVertex;
TVertex = record //опиываем одну вершину
fE :PTEdge; //начало списка рёбер выходящих из данной вершины
inputs :Integer; //количество выходящих из данной вершины рёбер
f1, f2 :Boolean; //какая-то херня
end;
TEdgeArray = array [1..1000] of PTEdge;
TVertexArray = array [1..1000] of PTVertex;
TGraph = record //тип граф
NV, NE :Integer; //количество вершин и рёбер и соотвтетственно массивы их содержащие
Edges :TEdgeArray;
Vertices :TVertexArray;
end;
var
G :TGraph;
function ReadGraph(fname :String) :TGraph; //считываем граф из файла
var
i :Integer; //в файле: в первой строке кол-во рёбер и вершин
f :Text; //в следующих описание каждого ребра
Res :TGraph;
begin
Assign(f, fname);
Reset(f);
with Res do begin
Readln(f, NE, NV);
for i := 1 to NV do begin
new(Vertices[i]);
with Vertices[i]^ do begin
fE := nil;
inputs := 0;
f1 := true;
end;
end;
for i := 1 to NE do begin
new(Edges[i]);
with Edges[i]^ do begin
Readln(f, b, e);
inc(Vertices[b]^.inputs);
next := Vertices[b]^.fE;
Vertices[b]^.fE := Edges[i];
end;
end;
end;
ReadGraph := Res;
end;
procedure dfsp(G :TGraph; p :Integer); //обычный обход в глубину с началом в вершине p
var
i :Integer;
begin
with G do begin
with Vertices[p]^ do begin
if (f1) then begin
write(p, ' ');
f1 := false; //f1 false если данная вершина рассматриваемая
end;
if ((inputs <> 0) and (f2)) then begin
f2 := false; //нахуй нужен f2 я не понял
dfsp(G, fE^.e);
end;
if (inputs <> 0) then begin
for i := p to NV do begin
Vertices[i]^.f2 := true;
end;
fE := fE^.next;
dec(inputs);
if (fE <> nil) then begin
dfsp(G, fE^.e);
end;
end;
end;
end;
end;
procedure dfs(G :TGraph);
var
i :Integer;
begin
with G do begin
for i := 1 to NV do begin
Vertices[i]^.f2 := true;
end;
for i := 1 to Vertices[1]^.inputs - 1 do begin
dfsp(G, 1);
end;
end;
end;
begin
G := ReadGraph('input.in');
dfs(G);
Readln;
end.