Question

无向图的邻接表存储方式和深度优先遍历的方法（代码）

Answer 1

type
node=record
y:longint;
flag:boolean;
next:longint;
p:-1..1;
end;
var
n,m,i,j,x,y:longint;
map:array [0..40000] of node;
a:array [0..40000] of longint;
procedure dfs(i:longint);
var
j:longint;
begin
j:=a[i];
while j>-1 do begin
if map[j].flag then begin
map[j].flag:=false;
map[j xor 1].flag:=false;
if map[j].p>-1 then begin
map[j].p:=0;
writeln(i);
dfs(map[j].y);
map[j].p:=1;
end;
end;
j:=map[j].next;
end;
end;

begin
readln(n,m);
for i:=1 to n do a[i]:=-1;
for j:=1 to m do begin
readln(x,y);
map[2*j-2].y:=y;
map[2*j-2].next:=a[x];
map[2*j-2].flag:=true;
a[x]:=2*j-2;
map[2*j-1].y:=x;
map[2*j-1].next:=a[y];
map[2*j-1].flag:=true;
a[y]:=2*j-1;
end;
map[a[1]].p:=0;
dfs(1);
map[a[1]].p:=1;
end.