Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var
- d, i, j, a, b : longint;
- n : longint; // Количество вершин.
- m : longint; // Количество рёбер.
- ecount : longint; // Счётчик рёбер.
- // Первое ребро в обходе.
- kick: array[1..100000] of longint;
- // Следующее ребро в обходе.
- next: array[0..200000] of longint;
- // Вершина, на которую указывает ребро.
- dest: array[0..200000] of longint;
- // Процедура добавления ориентированного ребра из вершины a до b.
- procedure addEdge(a:longint; b:longint);
- begin
- // Мы добавляем новое ребро под номером ecount.
- // Следующее за ecount ребро будет первое в обходе вершины a.
- next[ecount] := kick[a];
- // Направлено это ребро будет в вершину b.
- dest[ecount] := b;
- // Теперь первое ребро при обходе вершины a будет ecount.
- kick[a] := ecount;
- // Увеличиваем счётчик добавленных рёбер.
- inc(ecount);
- end;
- begin
- readln(n, m);
- ecount := 0; // Зануляем счётчик рёбер.
- // Для правильной работы нужно заполнить массив
- // kick числами -1, это означает что из вершин
- // в начале нет рёбер.
- for i := 1 to n do begin
- kick[i] := -1;
- end;
- for i := 1 to m do begin
- readln(a, b);
- // Добавляем два ориентированных ребра.
- // Это равносильно одному не ориентированному ребру.
- addEdge(a, b);
- addEdge(b, a);
- end;
- for i := 1 to n do begin
- ecount := 0; // Посчитаем количество соседей в ecount.
- j := kick[i]; // Начинаем обход вершины i с ребра kick[i].
- while j >= 0 do begin // Пока такое ребро существует...
- d := dest[j]; // Берём вершину, на которую указывает ребро j
- // Тут можно было бы использовать ребро из i в d,
- // но в этой задаче его нужно только посчитать.
- inc(ecount);
- j := next[j]; // Переходим к следующему ребру.
- end;
- // Выводим посчитанное количество соседей.
- writeln(ecount);
- end;
- end.
Advertisement
Add Comment
Please, Sign In to add comment