program adjlist;
           { Nachbarschafts-Liste eines ungerichteten Graphen }
uses crt;

const maxV = 'm';

type link = ^node;
     node = record
              v    : char;
              next : link;
            end;

var V,E,i      : integer;
    t,z        : link;
    adj_liste  : array['a'..maxV] of link;
    v1,v2,j    : char;



procedure read_adj_liste;
begin
 write('Anzahl der Knoten und Kanten des Graphen :  '); readln(V,E);
 writeln;writeln;
 new(z);
 z^.next:=z;
 for j:='a' to maxV do adj_liste[j]:=z;

 for i:=1 to E do
  begin
   write('die ',i:2,'.  Kante geht von  :  '); readln(v1);
   write('                   nach  :  ');      readln(v2);
   new(t); t^.v:=v1 ; t^.next:=adj_liste[v2] ; adj_liste[v2]:=t ;
   new(t); t^.v:=v2 ; t^.next:=adj_liste[v1] ; adj_liste[v1]:=t ;
  end;
end;



procedure print_adj_liste(Knoten : char);
var g: char;
    h: link;
begin
 new(h);
 for g:='a' to Knoten do
  begin
    h:=adj_liste[g];
    write('Knoten ',g,' :  ');
    while  (h^.next<>h ) do
      begin   write(h^.v ,'---'); h:=h^.next;   end;
    writeln('ende');
  end;
end;




procedure list_dfs;
var id, k : char;
    val   : array['a'..maxV] of char;

    procedure visit(k:char);
     var t: link;
     begin
      id:=chr(ord(id)+1);
      val[k]:=id;
      t:=adj_liste[k];
      while t<>t^.next do
        begin
         if val[t^.v]=' ' then begin  write(t^.v,'--'); visit(t^.v)  end;
         t:=t^.next;
        end;
     end;
begin
 id:='a';
 for k:='a' to maxV do val[k]:=' ';
 for k:='a' to maxV do
   if val[k]=' ' then  begin  writeln; visit(k); writeln(k);  end;
end;




begin
 clrscr;
 read_adj_liste;
 readln;
 clrscr;
 print_adj_liste(maxV);
 readln;
 writeln('                 Jetzt erfolgt Tiefensuche . ');writeln;
 list_dfs;
 readln;
end.