Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.01 KB | None | 0 0
  1. const
  2.     MAXN = 100000;
  3.     MAXM = 100000;
  4.    
  5. var
  6.     top, used: array [1..MAXN] of Integer;
  7.     e, next: array [1..MAXN + 2 * MAXM + 1] of Integer;
  8.     i, cur, v, n, m, a, b, nf, ans: Integer;
  9.    
  10. procedure addEdge(a, b: Integer);
  11. begin
  12.     e[top[a]] := b;
  13.     next[top[a]] := nf;
  14.     top[a] := nf;
  15.     Inc(nf);
  16. end;
  17.  
  18. procedure dfs(v: Integer);
  19. var
  20.     cur: Integer;
  21. begin
  22.     used[v] := 1;
  23.     cur := v;
  24.     while e[cur] <> -1 do begin
  25.         if used[e[cur]] = 0 then
  26.             dfs(e[cur]);
  27.         cur := next[cur];
  28.     end;
  29. end;
  30.    
  31. begin
  32.     ReadLn(n, m);
  33.     nf := n + 1;
  34.     for i := 1 to MAXN + 2 * MAXM + 1 do
  35.         e[i] := -1;
  36.     for i := 1 to n do begin
  37.         top[i] := i;
  38.         used[i] := 0;
  39.     end;
  40.     for i := 1 to m do begin
  41.         ReadLn(a, b);
  42.         addEdge(a, b);
  43.         addEdge(b, a);
  44.     end;
  45.     ans := 0;
  46.     for i := 1 to n do
  47.         if used[i] = 0 then begin
  48.             dfs(i);
  49.             Inc(ans);
  50.         end;
  51.     WriteLn(ans);
  52. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement