ADS - Quảng cáo

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program ADS;
Const
  input  = '';
  output = '';
  maxn = 20000;
  maxm = 50000;
Var
  free: array[1..maxn] of boolean;
  adj,x,y: array[1..maxm] of integer;
  h: array[1..maxn + 1] of integer;
  n,m: integer;

Procedure LoadGraph;
Var
  f: text;
  i: integer;
Begin
  Fillchar(h, sizeof(h), 0);
  Assign(f, input);
    Reset(f);

    Readln(f, n, m);
    For i:= 1 to m do
      Begin
        Readln(f, x[i], y[i]);
        inc(h[x[i]]);
        inc(h[y[i]]);
      End;
  Close(f);

  For i:= 2 to n do h[i]:= h[i] + h[i - 1];
  For i:= 1 to m do
    Begin
      adj[h[x[i]]]:= y[i];
      dec(h[x[i]]);
      adj[h[y[i]]]:= x[i];
      dec(h[y[i]]);
    End;
  h[n + 1]:= 2 * m;
End;

Procedure DFS(u: integer);
Var
  iv,v: integer;
Begin
  For iv:= h[u] + 1 to h[u + 1] do
    Begin
      v:= adj[iv];
      If free[v] then
        Begin
          free[v]:= false;
          DFS(v);
        End;
    End;
End;

Procedure solve;
Var
  f: text;
  i,cnt: integer;
Begin
  cnt:= 0;
  Fillchar(free, sizeof(free), true);
  For i:= 1 to n do if free[i] then
    Begin
      inc(cnt);
      free[i]:= false;
      DFS(i);
    End;

  Assign(f, output);
    Rewrite(f);
    Writeln(f, m - n + cnt);
  Close(f);
End;

Begin
  LoadGraph;
  solve;
End.

Download