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
program Project3;
{$APPTYPE CONSOLE}
uses
SysUtils;
type
PTEdge = ^TEdge;
TEdge = record //òèï îïèñûâàåò îäíî ðåáðî
b, e :Integer; //íà÷àëî è êîíåö ðåáðà
next :PTEdge; //ò.ê. âñå ð¸áðà ìû áóäåì õðàíèòü â âèäå ñïèñêà, òî next - îïèñûâàåò ñëåäóþùåå ðåáðîñ â ñïèñêå
end;
PTVertex = ^TVertex;
TVertex = record //îïèûâàåì îäíó âåðøèíó
fE :PTEdge; //íà÷àëî ñïèñêà ð¸áåð âûõîäÿùèõ èç äàííîé âåðøèíû
outs :Integer; //êîëè÷åñòâî âûõîäÿùèõ èç äàííîé âåðøèíû ð¸áåð
flag :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;
outs := 0;
flag := false;
end;
end;
for i := 1 to NE do begin
new(Edges[i]);
with Edges[i]^ do begin
Readln(f, b, e);
inc(Vertices[b]^.outs);
next := Vertices[b]^.fE;
Vertices[b]^.fE := Edges[i];
end;
end;
end;
ReadGraph := Res;
end;
procedure dfsP(G :TGraph; p :Integer);
var
CurrentEdge :PTEdge;
begin
if (G.Vertices[p]^.flag) then begin
exit;
end;
write(p, ' ');
G.Vertices[p]^.flag := true;
CurrentEdge := G.Vertices[p]^.fE;
while (CurrentEdge <> nil) do begin
dfsp(G, CurrentEdge^.e);
CurrentEdge := CurrentEdge^.next;
end;
end;
procedure dfs(G :TGraph);
var
i :Integer;
begin
with G do begin
for i := 1 to NV do begin
if (not Vertices[i]^.flag) then begin
dfsP(G, i);
end;
end;
end;
end;
begin
G := ReadGraph('input.in');
dfs(G);
Readln;
end.