HỌC TIN CÙNG THỦ KHOA

Mời các bạn Download code tại: Click here

1. File Input:Click here

- Dòng đầu tiên gồm duy nhất 1 số n là số đỉnh của đồ thị.

- n dòng tiếp theo, mỗi dòng gồm n số là ma trận trọng số của đồ thị, trong đó quy ước g[i, j] = 0 nếu không có đường đi trực tiếp từ i tới j.

2. File Output

- Gồm nhiều dòng, mỗi dòng 2 số u, v tương ứng là đỉnh đầu và đỉnh cuối của cạnh nằm trong cây khung.

const fi = 'CAYKHUNG.INP';
      fo = 'CAYKHUNG.OUT';
      MAXN = 10000;

var n, dem: integer;
    g: array [1..MAXN, 1..MAXN] of integer;
    cx: array [1..MAXN] of boolean;
    f: text;

procedure Nhap;
var i, j: integer;
begin
        assign(f, fi); reset(f);
        readln(f, n);
        for i:= 1 to n do
        begin
                for j:= 1 to n do
                        read(f, g[i, j]);
                readln(f);
        end;
        close(f);
end;

procedure Init;
begin
        fillchar(cx, sizeof(cx), true);
        dem:= 0;
end;

procedure DFS(u: integer);
var v: integer;
begin
        for v:= 1 to n do
                if cx[v] = true then
                        if g[u, v] = 1 then
                        begin
                                cx[v]:= false; // ra duy nhat 1 duong di
                                writeln(f, '(', u, ', ', v, ')');
                                inc(dem);
                                if dem = n-1 then exit
                                        else DFS(v);


                        end;
end;


BEGIN
        Nhap;
        Init;
        assign(f, fo); rewrite(f);
        cx[1]:= false;
        DFS(1);
        close(f);
END.