WEATHER – SPOJ

Đề bài: http://vn.spoj.com/problems/WEATHER/

Thuật toán:

• Bài này sử dụng thuật toán duyệt đồ thị DFS. Bạn có thể đọc code để hiểu rõ hơn.

Code:

{$inline on}
var
               n, m        :     longint;
               a           :     array[0..100, 0..100] of boolean;
               trace       :     array[0..100] of boolean;
               count       :     longint;

procedure      enter;
   var i, j, u, v: longint;
   begin
      readln(n);
      for i:= 1 to n do
         for j:= 1 to n do a[i, j]:= false;
      readln(m);

      for i:= 1 to m do
         begin
            readln(u, v);
            a[u, v]:= true;
            a[v, u]:= true;
         end;
   end;

procedure      dfs(u: longint);
   var i: longint;
   begin
      inc(count);
      trace[u]:= true;

      for i:= 1 to n do
         if a[u, i] and (not trace[i]) then dfs(i);
   end;

procedure      solve;
   var i, j, res, k: longint;
   begin
      res:= 0;

      for i:= 1 to n do
         for j:= i + 1 to n do
            if a[i, j] then
               begin
                  a[i, j]:= false;
                  a[j, i]:= false;

                  for k:= 1 to n do trace[k]:= false;
                  count:= 0;
                  dfs(1);

                  res:= res + count*(n - count);

                  a[i, j]:= true;
                  a[j, i]:= true;
               end;
      writeln(res);
   end;

begin
   enter;
   solve;
end.