bor

Neighbours Count

bor
Dec 9th, 2012
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 2.55 KB | None | 0 0
  1. var
  2.  d, i, j, a, b : longint;
  3.  n : longint; // Количество вершин.
  4.  m : longint; // Количество рёбер.
  5.  ecount : longint; // Счётчик рёбер.
  6.  // Первое ребро в обходе.
  7.  kick: array[1..100000] of longint;
  8.  // Следующее ребро в обходе.
  9.  next: array[0..200000] of longint;
  10.  // Вершина, на которую указывает ребро.
  11.  dest: array[0..200000] of longint;
  12.  
  13. // Процедура добавления ориентированного ребра из вершины a до b.
  14. procedure addEdge(a:longint; b:longint);
  15. begin
  16.   // Мы добавляем новое ребро под номером ecount.
  17.   // Следующее за ecount ребро будет первое в обходе вершины a.
  18.   next[ecount] := kick[a];
  19.   // Направлено это ребро будет в вершину b.
  20.   dest[ecount] := b;
  21.   // Теперь первое ребро при обходе вершины a будет ecount.
  22.   kick[a] := ecount;
  23.   // Увеличиваем счётчик добавленных рёбер.
  24.   inc(ecount);
  25. end;
  26.  
  27. begin
  28.   readln(n, m);
  29.   ecount := 0; // Зануляем счётчик рёбер.
  30.   // Для правильной работы нужно заполнить массив
  31.   // kick числами -1, это означает что из вершин
  32.   // в начале нет рёбер.
  33.   for i := 1 to n do begin
  34.     kick[i] := -1;
  35.   end;
  36.  
  37.   for i := 1 to m do begin
  38.     readln(a, b);
  39.     // Добавляем два ориентированных ребра.
  40.     // Это равносильно одному не ориентированному ребру.
  41.     addEdge(a, b);
  42.     addEdge(b, a);
  43.   end;
  44.  
  45.   for i := 1 to n do begin
  46.     ecount := 0; // Посчитаем количество соседей в ecount.
  47.     j := kick[i]; // Начинаем обход вершины i с ребра kick[i].
  48.     while j >= 0 do begin // Пока такое ребро существует...
  49.       d := dest[j]; // Берём вершину, на которую указывает ребро j
  50.       // Тут можно было бы использовать ребро из i в d,
  51.       // но в этой задаче его нужно только посчитать.
  52.       inc(ecount);
  53.       j := next[j]; // Переходим к следующему ребру.
  54.     end;
  55.     // Выводим посчитанное количество соседей.
  56.     writeln(ecount);
  57.   end;
  58. end.
Advertisement
Add Comment
Please, Sign In to add comment