Задача A1. Лекция. Графы. Определения ≡

Условие

Ориентированный граф (directed graph) определяется как пара множеств (V,E), где V — конечное множество, а E — множество всех пар элементов из V, т.е. подмножество множества V × V. Ориентированный граф иногда для краткости называют орграфом (digraph). Множество V называют множеством вершин графа (vertex set); его элемент называют вершиной графа (vertex; множественное число vertices). Множество E называют множеством ребер (edge set) графа; его элементы называют ребрами (edges). На рисунке 1(а) показан ориентированный граф с множеством вершин {1,2,3,4,5,6}. Вершины изображены кружками, а ребра — стрелками. Заметим, что граф может содержать ребра-петли (self-loops), соединяющие вершину с собой.

В неориентированном (undirected) графе G = (V, E) множество ребер E состоит из неупорядоченных (unordered) пар вершин: парами являются множества {u, v}, где u, v ∈ V и u ≠ v. Мы будем обозначать неориентированное ребро как (u, v) вместо {u, v}; при этом для неориентированного графа (u, v) и (v, u) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин. На рисунке 1(б) изображен неориентированный граф с множеством вершин {1,2,3,4,5,6}.

Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (u, v) ориентированного графа говорят, что оно выходит из (incident from, leaves) вершины u и входит в (incident to, enters) вершину v. Например, на рис. 1(а) имеется три ребра, выходящих из вершины 2 ((2,2), (2,4), (2,5)) и два ребра, в нее входящих ((1,2), (2,2)). Про ребро (u, v) неориентированного графа говорят, что оно инцидентно вершинам (incident on vertices) u и v. Например, на рис. 1 (б) есть два ребра, инцидентные вершине 2 (ребра (1,2) и (2,5)).

Если в графе G имеется ребро (u, v), говорят, что вершина v смежна с вершиной u (is adjacent to u). Если вершина v смежна с вершиной u в ориентированном графе, пишут u→ v. Для обоих рисунков 1(а) и 1(б) вершина 2 является смежной с вершиной 1, но лишь во втором из них вершина 1 смежна с вершиной 2 (в первом случае ребро (2,1) отсутствует в графе).

Степенью (degree) вершины в неориентированном графе называется число инцидентных ей ребер. Например, для графа рис. 1(б) степень вершины 2 равна 2. Для ориентированного графа различают исходящую степень (out-degree), определяемую как число выходящих из нее ребер, и входящую степень (in-degree), определяемую как число входящих в нее ребер. Сумма исходящей и входящей степени называется степенью вершины. Например, вершина 2 в графе рис. 1(а) имеет входящую степень 2, исходящую степень 3 и степень 5.

Путь длины k (path of length k) из вершины u в вершину v определяется как последовательность вершин 〈 v₀, v₁, v₂, ..., v_k〉, в которой v₀ = u, v_k = v и (v_i − 1, v_i) ∈ E для всех i = 1,2,…,k. Этот путь содержит (contains) вершины v₀, v₁,...,v_k и ребра (v₀, v₁), (v₁,v₂),...,(v_k − 1,v_k). Вершину v₀ называют началом пути, вершину v_k — его концом;говорят, что путь ведет из v₀ в v_k. Если для данных вершин u и u′ существует путь p из u в u′, то говорят, что вершина u′ достижима из u по пути p (u′ is reachable from u via p).

Циклом (cycle) в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл 〈 v₀, v₁, ..., v_k〉 называется простым, если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины v₁, v₂,...,v_k различны. Ребро-петля является циклом длины 1. Мы отождествляем циклы, отличающиеся сдвигом вдоль цикла: один и тот же цикл длины k может быть представлен k различными путями (в качестве начала и конца можно взять любую из k вершин). Например, на рис. 1(а) пути 〈 1, 2, 4, 1〉, 〈 2,4,1,2〉 и 〈 4,1,2,4〉 представляют один и тот же цикл. Этот цикл является простым, в то время как цикл 〈 1,2,4,5,4,1〉 таковым не является. На том же рисунке есть цикл 〈 2,2〉, образованный единственный ребром-петлей (2,2).

В неориентированном графе путь 〈 v₀, v₁, ..., v_k〉 называется (простым) циклом, если k ≥ 3, v₀ = v_k и все вершины v₁, … , v_k различны. Например, на рис. 1(б) имеется простой цикл 〈 1, 2, 5, 1〉.

Граф, в котором нет циклов, называется ациклическим (acyclic).

Неориентированный граф называется связным (connected), если для любой пары вершин существует путь из одной в другую. Максимальные по включению (нельзя добавить ни одной вершины, сохранив связность) связные подграфы называются связными компонентами (connected components) графа. Например, на рис. 1(б) имеется три связные компоненты: {1,2,5}, {3,6} и {4}. Неориентированный граф связен тогда и только тогда, когда он состоит из единственной связной компоненты.

Ориентированный граф называется сильно связным (strongly connected), если из любой его вершины достижима (по ориентированным путям) любая другая. Любой ориентированный граф можно разбить на сильно связные компоненты, которые определяются как максимальные по включению сильно связные подграфы. Ориентированный граф сильно связен тогда и только тогда, когда состоит из единственной сильно связной компоненты. Граф на рис. 1(а) имеет три таких компоненты: {1,2,4,5}, {3} и {6}. Заметим, что вершины {3,6} не входят в одну сильно связную компоненту, так как 3 достижима из 6, но не наоборот.

Упражнения

Покажите, что сумма степеней любого графа четна.

Покажите, что число нечетных вершин любого графа четно.

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

Покажите, что для любого связного неориентированного графа G = (V, E) выполняется соотношение |E| ≥ |V| − 1.

В графе G = (V, E) любая пара вершин соединена либо ребром красного цвета, либо ребром зеленого цвета. Пусть G₁ — подграф графа G, состоящий только из ребер зеленого цвета и инцидентных им вершин. Пусть, аналогично, G₂ — подграф, состоящий только из ребер красного цвета. Покажите, что либо G₁, либо G₂ является связным.

Подсказка (выделите текст, чтобы прочесть): Между любыми двумя вершинами в вышеописанном графе G существует либо полностью зеленый, либо полностью красный путь, состоящий из не более, чем двух ребер.

Задача A2. Лекция. Графы. Способы представления ≡

Условие

Рассмотрим граф G(V, E) с n = |V| вершинами v₁, ..., v_n. Его матрицей смежности (adjacency matrix) называется (n × n) — матрица a, в которой a_ij = { 1, если (v_i, v_j) ∈ E0 иначе.

Матрица смежности неориентированного графа, таким, образом, симметрична. В таком представлении мы можем за время O(1) проверить, соединены ли данные вершины ребром (посмотрев на один элемент массива). В то же время хранение матрицы требует памяти O(n²), что во многих случаях неэкономно.

Пример кода для считывания графа с n вершинами и m рёбрами в матрицу смежности.

var
    adj: array of array of Boolean;
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n, n);
    for i := 1 to m do begin
        Read(u, v);
        adj[u, v] := true;
        adj[v, u] := true;
    end;
end.

Альтернативное представление — список смежности (adjacency list). Требуемая при этом память пропорциональна размеру графа (сумме числа вершин и числа ребер). Элементами списка смежности являются массивы, по одному для каждой вершины графа. Для вершины u в таком списке хранятся вершины, в которые ведут ребра из u, т.е. вершины v, для которых (u, v) ∈ E. Для ориентированного графа каждое ребро входит только в один из этих списков (для начальной вершины), а для неориентированного — в два (для двух концов ребра). Список смежности, таким образом, требует памяти O(V + E). Проверка наличия ребра (u, v) теперь требует просмотра списка вершины u (что может быть больше O(1) шагов). Зато в этом представлении легко просмотреть всех соседей заданной вершины (что часто бывает необходимо). Список смежности для неориентированного графа симметричен (если u содержится в списке для v, то и v содержится в списке для u).

Пример кода для считывания графа с n вершинами и m рёбрами в список смежности.

var
    adj: array of array of Integer;

procedure Add(a, b: integer) begin
    SetLength(adj[a], Length(adj[a]) + 1);
    adj[a, High(adj[a])] = b;
end;

var
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n);
    for i := 1 to m do begin
        Read(u, v);
        Add(u, v);
        Add(v, u);
    end;
end.

std::vector< std::vector< int>> adj;
int n, m;
std::cin >> n >> m;
adj.resize(n);
for(int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
        

Матрица смежности или список смежности?

Что лучше? Ответ зависит от отношения между числом вершин |V| и числом ребер |E|. Заметим, что |E| может быть довольно малым — порядка |V| (если |E| сильно меньше |V|, то граф уже вырожденный — в частности, содержит изолированные вершины). Или же довольно большим — порядка |V|² (если граф содержит все возможные ребра). Графы с большим числом ребер называют плотными (dense), с малым — разреженными (sparse).

Выбирая алгоритм, полезно понимать, с какими графами ему в основном придется иметь дело. Важно это и при хранении: если хранить веб-граф, в котором больше восьми миллиардов вершин, в виде матрицы смежности, то занимать она будет миллионы терабайтов, что сравнимо с общей емкостью всех жестких дисков в мире. И дальше, скорее всего, будет только хуже (матрица может расти быстрее, чем производство дисков).

А вот хранить граф Интернета в виде списка смежности вполне разумно, поскольку хранить нужно несколько десятков миллиардов гиперссылок, каждая из которых будет занимать в списке всего несколько байтов, и такого размера диск поместится в карман. Такая разница происходит из-за того, что граф Интернета очень разрежен: страница содержит в среднем пару десятков ссылок на другие страницы — из нескольких миллиардов возможных.

Задача A3. Лекция. Графы. Поиск в глубину ≡

Условие

Прохождение лабиринтов

Поиск в глубину (depth-first search) отвечает на вопрос: какие части графа достижимы из заданной вершины? Это похоже на задачу обхода лабиринта: имея граф, как список смежности, мы в каждой вершине "видим" ее соседей — как в лабиринте, где мы видим соседние помещения (рис. 1) и можем в них перейти. Но если мы будем это делать без продуманного плана, то можем ходить кругами, а в какую-то часть так и не попасть.

Обойти лабиринт можно с помощью клубка ниток (закрепив конец нитки в исходной точке и нося клубок с собой, мы всегда сможем вернуться) и мела (чтобы отмечать, где мы уже были, и не ходить туда еще раз). Примерно так же работает алгоритм поиска в глубину. Чтобы хранить пометки, для каждой вершины будем хранить бит, показывающий, были мы в этой вершине или нет. Клубок ниток можно было бы заменить стеком (идя в новый коридор, мы добавляем его в стек, а возвращаясь обратно, забираем), но в нашем алгоритме (рис. 2) мы вместо явного стека используем рекурсию.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    { Эта функция зависит от конкретной задачи }
    { В ней или вместо нее может быть любой код, вызывающийся при посещении новой вершины }
    Previsit(v);

    { Граф хранится списками смежности (массив adj) }
    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

   { Эта функция также зависит от конкретной задачи }
    Postvisit(v);
end;

В нашем алгоритме указано также место для процедур Previsit и Postvisit (вызываемых до и после обработки вершины); мы увидим дальше, зачем это может быть полезно.

А пока нужно убедиться, что процедура Explore корректна. Ясно, что она обходит только достижимые из v вершины, поскольку на каждом шаге она переходит от вершины к ее соседу. Но обходит ли она все такие вершины? Допустим, что нашлась достижимая из v вершина u, до которой Explore почему-то не добралась. Рассмотрим тогда какой-нибудь путь из v в u. Пусть z — последняя вершина этого пути, которую посетила процедура Explore (сама вершина v, если других нет), а w — следующая сразу за z вершина на этом пути: (рис. 3).

Выходит, что вершину z процедура посетила, а вершину w — нет. Но так быть не может: ведь состоявшийся вызов Explore(z) должен был перебрать всех соседей z.

На рис. 4 показан вызов Explore для рассмотренного ранее графа и вершины A. Считаем, что соседи вершины перебираются в алфавитном порядке. Сплошными нарисованы ребра, которые ведут в ранее не встречавшиеся вершины. Например, когда процедура Explore находилась в вершине B, она прошла по ребру B − E, и, поскольку в E она до этого не бывала, был произведен вызов Explore для E. Сплошные ребра образуют дерево (связный граф без циклов) и поэтому называются древесными ребрами (tree edges). Пунктирные же ребра ведут в вершины, которые уже встречались. Такие ребра называются обратными (back edges).

Поиск в глубину

procedure Dfs;
var
    v: Integer;
begin
    for v := 1 to MaxV do
        if not used[v] then
            Explore(v);
end;

Процедура Explore обходит все вершины, достижимые из данной. Для обхода всего графа алгоритм поиска в глубину (рис. 5) последовательно вызывает Explore для всех вершин (пропуская уже посещенные).

Сразу же отметим, что процедура Explore вызывается для каждой вершины ровно один раз благодаря массиву used (пометки в лабиринте). Сколько времени уходит на обработку вершины? Она включает в себя:

• O(1)-операции: пометка вершины, а также вызовы Previsit и Postvisit (мы не учитываем время внутри этих вызовов);
• перебор соседей.

Общее время зависит от вершины, но можно оценить количество операций для всех вершин вместе. Общее количество операций на шаге 1 есть O(|V|). На шаге 2 (будем говорить о неориентированном графе) каждое ребро x,y ∈ E просматривается ровно два раза: при вызовах Explore(x) и Explore(y). Общее время работы на шаге 2, таким образом, есть O(|E|). В целом время работы поиска в глубину есть O(|V| + |E|), то есть линейно. За меньшее время мы не успеем даже прочесть все вершины и ребра.

Задача A4. Лекция. Графы. DFS в ориентированном графе. ≡

Условие

Поиск в глубину в ориентированном графе

Рассмотренный нами алгоритм поиска в глубину может быть использован и для ориентированных графов (в процедуре Explore надо перебирать выходящие из вершины ребра). На рис. 1 показан пример ориентированного графа и дерева, построенного поиском в глубину.

Вершина A называется корнем дерева (tree root), все остальные вершины этого дерева являются ее потомками E, а E является их предком (ancestor). Наконец, C является родителем (parent) D, а D — ребенком (child) C. (В отличие от людей, у вершины дерева может быть только один родитель.)

При поиске в глубину в ориентированных графах различают четыре типа ребер.

• Ребра дерева (tree edges) — ребра леса, построенного поиском в глубину.
• Прямые ребра (forward edges) ведут от вершины к ее потомку, не являющемуся при этом ее ребенком.
• Обратные ребра (back edges) ведут от вершины к ее предку.
• Перекрестные ребра (cross edges) ведут от вершины к другой вершине, не являющейся ни предком, ни потомком первой (такая вершина уже полностью обработана в момент обнаружения перекрестного ребра).

На рис. 1 можно обнаружить два прямых, два обратных и два перекрестных ребра (найдите их).

Тип ребра можно узнать по tin и tout значениям его концов. Легко видеть, что вершина u является предком v тогда и только тогда, когда v была обнаружена во время вызова Explore(u). В этом случае tin(u) < tin(v) < tout(v) < tout(u), то есть отрезок обработки v вложен в отрезок обработки u. Для обратных ребер: u — потомок v тогда и только тогда, когда v — предок u; для перекрестных ребер u − v отрезки не пересекаются (и v-отрезок предшествует u-отрезку).

Могут ли быть другие случаи расположения отрезков? Почему?

Ориентированные ациклические графы

Наличие циклов в ориентированном графе легко проверить с помощью одного вызова поиска в глубину.

Свойство. Ориентированный граф содержит цикл тогда и только тогда, когда при поиске в глубину обнаруживается обратное ребро.

Доказательство. Ясно, что если (u, v) — обратное ребро, то путь в дереве поиска в глубину от v к u и само ребро (u, v) образуют цикл.

Обратно: пусть граф содержит цикл v₀→ v₁→ ... → v_k→ v₀ и пусть v_i — вершина этого цикла, которая была обнаружена первой (то есть вершина с минимальным tin(v_i)). Все оставшиеся вершины цикла достижимы из v_i, и поэтому в дереве поиска в глубину они будут потомками v_i. Тогда ребро v_i − 1→ v_i (или же v_k→ v₀, если i = 0) ведет из вершины в ее предка, то есть является обратным ребром.

Топологическая сортировка

С помощью ориентированных ациклических графов (directed acyclic graphs или сокращенно DAGs) удобно представлять временные и иерархические отношения, а также причинно-следственные связи. Допустим, к примеру, что необходимо сделать несколько вещей, при чем есть ограничения на порядок (сначала надо проснуться и лишь потом встать с кровати; душ надо принять после того, как встал с кровати, но до того, как оделся). Как выбрать правильный порядок дел?

Ограничения представим как ориентированный граф: каждому делу соответствует вершина; ребро из u в v означает, что u должно быть выполнено до v. Если в этом графе есть цикл, то правильного порядка не существует вовсе. Если же граф ациклический, то есть надежда его топологически упорядочить (topologically sort) — так упорядочить вершины, чтобы каждое ребро вело от более ранней вершины к более поздней. Например, для графа рис. 2 один из допустимых порядков таков: B, A, D, C, E, F. (Видите ли вы еще три порядка?).

Какие же ориентированные ациклические графы можно топологически упорядочить? Оказывается, что все, и это можно сделать с помощью поиска в глубину, расположив вершины в порядке убывания их tout-значений. Ведь tout(u) < tout(v) только для обратных ребер (u, v), а мы уже знаем, что в ациклическом графе обратных ребер быть не может.

Свойство.В ориентированном ациклическом графе каждое ребро идет из вершины с бОльшим tout-значением в вершину с меньшим tout-значением.

Посмотрим на первую и последнюю вершину после топологической сортировки. Из последней вершины рёбра не выходят: как говорят, она является стоком (sink). Напротив, в первую вершину рёбра не входят: она является истоком (source). В частности, мы доказали такое утверждение:

Свойство.У каждого ациклического ориентированного графа есть хотя бы один исток и хотя бы один сток.

Заметим, что, отсортировать вершины по значению tout можно за линейное время. Для этого нужно добавлять вершины в массив в момент выхода из функции Explore

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

{ Добавляем вершину в конец с помощью глобального счетчика k }
    order[k] = v;
    k += 1;
end;

Задача AA. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

Формат входного файла

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

Формат выходного файла

Выходной файл должен содержать число получившихся после сборки программ.

Ограничения

Примеры тестов

3 1
2 3

2

Задача AB. Конвертер графов ≡

Условие

Вам требуется написать программу, принимающую на вход ориентированный граф в заданном формате и выводящую этот же граф в заданном (возможно, другом) формате. Граф может содержать петли, но не содержит кратных ребер.

Формат входного файла

Первая строка входного файла содержит два слова. Первое — название формата графа во входном файле. Второе — название формата, в котором граф необходимо вывести.

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

• edges — список ребер. В этом случае первая строка описания графа должна содержать два целых числа N, M — количество вершин и количество ребер соответственно. Далее каждая следующая строка содержит два числа u и v — начало и конец очередного ребра.
• lists — списки смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее i-я строка (начиная со второй) содержит описание списка смежности (i − 1)-й вершины. Первое целое число в строке c_i — количество вершин, в которые выходят ребра из (i − 1)-й вершины. Далее через пробел следует c_i целых чисел — номера вершин, в которые выходят ребра из (i − 1)-й.
• mat — матрица смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее следует N строк по N чисел 0 или 1 — описание матрицы смежности. Если в i-й строке на j-й позиции находится единичка, значит в графе есть ребро из (i − 1)-й вершины в j-ю.

Формат выходного файла

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N²

Примеры тестов

edges mat
3 4
1 2
2 3
1 3
2 2

3
0 1 1
0 1 1
0 0 0

mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0

4
3 1 3 4
0
2 1 2
2 2 3

Задача B1. Лекция. Графы. DFS. Времена входа и выхода ≡

Условие

Времена входа и выхода при обходе в глубину

Вспомним процедуру обхода графа в глубину.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;
    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

    Postvisit(v);
end;

Поиск в глубину позволяет за линейное время определить, связен ли граф. Но это далеко не все — сейчас мы рассмотрим прием, который лежит в основе многих других применений поиска в глубину. Будем записывать время входа в каждую вершину (вызов Previsit) и время выхода (Postvisit). Для нашего примера эти числа показаны на рис. 1. Например, в момент времени 5 началась обработка вершины I, а в момент времени 21 закончилась обработка вершины D.

Чтобы сохранить эту информацию при поиске в глубину, заведем счетчик time, изначально равный 1, и напишем так:

procedure Previsit(v: integer);
begin
    tin[v] := time;
    time += 1;
end;

procedure Postvisit(v: integer);
begin
    tout[v] := time;
    time += 1;
end;

Рассмотрим отрезки на числовой прямой, образованные временами входа и выхода в каждую из вершин.

Свойство. Для любых двух вершин u и v либо отрезки [tin(u), tout(u)] и [tin(v), tout(v)] не пересекаются, либо один содержится в другом.

В самом деле, [tin(u), tout(u)] — это промежуток времени, в течение которого вершина u была в стеке, и если вершина v была помещена в стек, когда там уже лежала вершина u, то v будет вынута раньше u.

Таким образом, рассмотренные отрезки отражают структуру дерева, построенного при поиске в глубину.

Задача B2. Лекция. Графы. Поиск в ширину ≡

Условие

Кратчайшие пути

Поиск в глубину не только быстро находит все вершины, достижимые из начальной, но и строит дерево, содержащее пути к ним (рис. 1). Однако эти пути не обязательно будут кратчайшими: например, от S до C можно добраться по одному ребру, в то время как поиск в глубину находит путь из трех.

Расстоянием(distance) между двумя вершинами неориентированного графа будем называть длину кратчайшего пути между ними, измеренную в ребрах. У этого понятия есть простой физический смысл. Представим себе граф из шариков (вершин), соединенных нитками одинаковой длины (ребрами). Потянем граф вверх за вершину s; за ней потянутся все вершины, достижимые из s. Чтобы найти расстояния от них до s, мы можем теперь просто измерить, насколько они ниже s.

Например, на (рис. 2) расстояние между вершинами S и B равно 2, и есть два кратчайших пути между ними. Когда граф подвешен за S, все ребра этих двух путей натягиваются. А ребро (D, E) провисает, поскольку не входит ни в один из кратчайших путей из вершины S.

Поиск в ширину

Вершины графа рис. 2, подвешенного за S, разбиваются на слои: сама S, вершины на расстоянии 1 от S, вершины на расстоянии 2 и так далее. Можно находить расстояния от S до всех вершин, переходя от уровня к уровню. Когда вершины уровней 0, 1, 2, ..., d определены, легко найти вершины уровня d + 1: это просто еще не просмотренные вершины, смежные с вершинами уровня d. Эти рассуждения наталкивают нас на алгоритм, работающий в каждый момент с двумя уровнями: некоторым уровнем d, который уже полностью известен, и уровнем d + 1, который находится просмотром соседей вершин уровня d.

Для необходимого порядка просмотра вершин нам понадобится структура данных очередь. В такой структуре данных есть три операции:

• Push — добавить элемент в конец очереди
• Pop — удалить начальный элемент очереди (данная функция также возвращает удаленный элемент)
• Empty — узнать, пуста ли очередь

procedure Push(v: integer);
begin
    q[qend] := v;
    qend += 1;
end;

function Pop(): integer;
begin
    Result := q[qbegin];
    qbegin += 1;
end;

function Empty(): boolean;
begin
    Result := (qbegin = qend);
end;

Поиск в ширину (breadth-first search, BFS) непосредственно реализует вышеописанную идею обхода вершин (рис. 4). Изначально очередь Q содержит только вершину S, то есть вершину на расстоянии 0. Для каждого последующего расстояния d = 1, 2, 3, ... найдется момент времени, в который Q содержит все вершины на расстоянии d и только их. Когда все эти вершины будут обработаны (извлечены из очереди), их непросмотренные соседи окажутся добавленными в конец очереди, то есть мы перейдем к следующему значению d.

procedure bfs(start: integer);
var
    i, u, v: integer;
begin
    Push(start);

    used[start] := true;
    dist[start] := 0;

    while not Empty() do begin
        u = Pop();

        for i := 0 to High(adj[u]) do begin
            v = adj[u][i];

            if not used[v] then begin
                used[v] := true;
                Push(v);
                dist[v] := dist[u] + 1;
            end;
        end;
    end;
end;

Запустим этот алгоритм для вершины S в графе (рис. 1). Считаем, что соседи каждой вершины обрабатываются в алфавитном порядке. На (рис. 5) слева показан порядок обхода вершин, а справа изображено дерево поиска в ширину. Оно содержит только ребра, при переходе по которым обнаруживались новые вершины. В отличие от дерево поиска в глубину все пути данного дерева с началом в S являются кратчайшими. Поэтому оно называется деревом кратчайших путей (shortest-path tree).

Порядок обхода	Содержание очереди
	[S]
S	[A~C~D~E]
A	[C~D~E~B]
C	[D~E~B]
D	[E~B]
E	[B]
S	[]

Этот алгоритм можно применять и к ориентированным графам. В них тоже можно определить расстояние от вершины S до вершины T как минимальное число ребер, которое надо пройти (в их направлении), чтобы из S попасть в T. Расстояние при этом уже не будет симметрично, но понятие кратчайшего пути имеет смысл, и наш алгоритм по-прежнему годится.

Корректность и время работы

Убедимся в корректности алгоритма. Мы утверждаем, что для всех d = 0, 1, 2, ... найдется момент времени, когда:

1. для всех вершин на расстоянии не более d это расстояние уже помещено в массив dist;
2. для всех оставшихся вершин значения в dist равны ∞ (бесконечность);
3. очередь содержит в точности вершины на расстоянии d.

Данное утверждение легко доказывается по индукции (проверьте).

Как и в случае поиска в глубину, время работы поиска в ширину линейно, то есть равно O(|V| + |E|). Действительно, каждая вершина помещается в очередь ровно один раз — при ее обнаружении. Поэтому общее количество операций с очередью есть 2|V|. Вся оставшаяся работы производится во внутреннем цикле алгоритма. На это требуется время O(|E|), поскольку каждое ребро в данном цикле просматривается один раз (для ориентированных графов) или два раза для неориентированных).

Теперь, когда знаем и поиск в глубину, и поиск в ширину, интересно сравнить их способы обхода графа. Поиск в глубину стремится вперед, и возвращается назад, чтобы пойти вбок, только если впереди уже нет новых вершин. Поэтому он может долго добираться до вершины, которая находится совсем близко (рис. 1). Поиск в ширину обходит вершины в порядке увеличения расстояний до них от начальной вершины, как фронт волны на воде.

Если в алгоритме поиска в ширину заменить очередь на стек (вынимается первым тот элемент, который положен последним), то он превратится в поиск в глубину (в нерекурсивном варианте).

При поиске в ширину нас интересуют расстояния от s, поэтому мы не перезапускаем поиск в других связных компонентах (недоступные вершины просто игнорируются).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Problem BA. Topological sorting ≡

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

Sample tests

4 3
1 2
1 3
3 4

1 3 2 4

Задача BB. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4 3
1 2
1 3
3 4

1 3 2 4

Problem BC. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Problem BD. Fast Dijkstra ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Problem BF. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

Problem BG. Floyd-Warshall ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 5
1 3 10
2 3 2

0 5 7
  0 2
    0

Problem BH. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Problem BI. Shortest Spanning Tree ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Problem BJ. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача CA. Перестройка ≡

Условие

В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

• между любыми двумя городами не больше одной дороги;
• никакая дорога не соединяет город с самим собой.

После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:

• разрушить одну из существующих дорог;
• построить новую дорогу, которой раньше не было, не ведущую из города в него же.

Кроме этого, для улучшения экономических связей между городами, правительство хочет, чтобы после принятия дорожной реформы можно было добраться из любого города в любой другой. При этом не гарантируется, что это требование выполнялось до реформы.

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

Формат входного файла

Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа a_i, b_i  — номера городов, которые соединяет i-я дорога.

Формат выходного файла

Выведите одно целое число  — количество способов провести реформу.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ a_i, b_i ≤ N, a_i ≠ b_i

Задача CB. Метро ≡

Условие

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

Формат входного файла

Во входном файле записано сначала число N — количество станций метро в городе. Далее записано число M — количество линий метро. Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

В конце файла записаны два различных: числа A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Формат выходного файла

Ограничения

Примеры тестов

5 2
4 1 2 3 4
2 5 3
3 1

0

5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5

2

10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8

1

4 2
2 1 2
2 3 4
1 3

-1

Задача D. Очное посещение RuCode ≡

Условие

По 1 баллу в день, включая турнир.