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

Условие

G 1 1 2 2 1->2 2->2 4 4 2->4 5 5 2->5 4->1 4->5 5->4 6 6 3 3 6->3
а.
G 1 1 2 2 1--2 5 5 2--5 5--1 4 4 3 3 6 6 3--6
б.
с.
Рис 1. Ориентированные и неориентированные графы

Ориентированный граф (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 определяется как последовательность вершин 〈 v0, v1, v2, ..., vk, в которой v0 = u, vk = v и (vi − 1, vi) ∈ E для всех i = 1,2,…,k. Этот путь содержит (contains) вершины v0, v1,...,vk и ребра (v0, v1), (v1,v2),...,(vk − 1,vk). Вершину v0 называют началом пути, вершину vk — его концом;говорят, что путь ведет из v0 в vk. Если для данных вершин u и u существует путь p из u в u, то говорят, что вершина u достижима из u по пути p (u is reachable from u via p).

Циклом (cycle) в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл 〈 v0, v1, ..., vk называется простым, если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины v1, v2,...,vk различны. Ребро-петля является циклом длины 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).

В неориентированном графе путь 〈 v0, v1, ..., vk называется (простым) циклом, если k ≥ 3, v0 = vk и все вершины v1, … , vk различны. Например, на рис. 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) любая пара вершин соединена либо ребром красного цвета, либо ребром зеленого цвета. Пусть G1 — подграф графа G, состоящий только из ребер зеленого цвета и инцидентных им вершин. Пусть, аналогично, G2 — подграф, состоящий только из ребер красного цвета. Покажите, что либо G1, либо G2 является связным.

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


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

Условие

Рассмотрим граф G(V, E) с n = |V| вершинами v1, ..., vn. Его матрицей смежности (adjacency matrix) называется (n × n) — матрица a, в которой aij = 1, если (vi, vj) ∈ E0 иначе.

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

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

Pascal C++

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.
std::vector< std::vector< bool>> adj; int n, m; std::cin >> n >> m; adj.resize(n, n); for(int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; adj[u][v] = true; adj[v][u] = true; }

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

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

Pascal C++
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|2 (если граф содержит все возможные ребра). Графы с большим числом ребер называют плотными (dense), с малым — разреженными (sparse).

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

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


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

Условие

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

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

Рис 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;
Рис 2. Нахождение всех вершин, достижимых из данной

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

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

Рис 3. Путь из v в u

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

Рис 4. Результат вызова функции Explore(A) для графа с рис. 1.

На рис. 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;
Рис 5. Поиск в глубину

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

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

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


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

Условие

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

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

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

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

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

На рис. 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) образуют цикл.

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

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

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

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

Рис 2. Ориентированный граф с одним источником, двумя стоками и четырьмя возможными топологическими сортировками

Какие же ориентированные ациклические графы можно топологически упорядочить? Оказывается, что все, и это можно сделать с помощью поиска в глубину, расположив вершины в порядке убывания их 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. Модули

Автор:И. Олейников   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
2

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

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
edges mat
3 4
1 2
2 3
1 3
2 2
3
0 1 1
0 1 1
0 0 0
2
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. Времена входа и выхода

Условие

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

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

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

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. Лекция. Графы. Поиск в ширину

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

а.
б.
Рис 1. (а) Граф и (б) его дерево поиска в глубину.

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

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

а.
б.
Рис 2. (а) Граф и (б) его "подвешенный" за вершину 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.

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

Такую структуру данных легко реализовать с помощью массива (рис. 3).

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;
Рис. 3. Реализация очереди с помощью массива и пары индексов — начала и конца

Поиск в ширину (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;
Рис. 4. Реализация алгоритма поиска в ширину

Запустим этот алгоритм для вершины 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[]
а.
б.
Рис. 5. Результат поиска в ширину для графа рис. 1

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2

Problem BA. Topological sorting

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

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

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:20 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит числа N и M - количество чиновников и "условий" соответственно. Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.

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

Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников. Если такой последовательности не существует (бывает же и такое!), выведите  − 1.

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

Problem BC. Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem BD. Fast Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed 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 arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem BF. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Problem BG. Floyd-Warshall

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
  0 2
    0

Problem BH. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain  − 1.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

Problem BI. Shortest Spanning Tree

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Problem BJ. SST for sparse graph

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:10 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

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

Автор:Russian Code Cup 2012   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

0 ≤ M ≤ 2 ⋅ 105

1 ≤ ai, bi ≤ N, ai ≠ bi


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

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:e.in   Ограничение памяти:64 Мб
Выходной файл:e.out  

Условие

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

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

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

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

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

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

В выходной файл выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, выведите в выходной файл одно число  − 1 (минус один).

Ограничения

2 ≤ N ≤ 100, 1 ≤ M ≤ 20, 2 ≤ Pi ≤ 50.

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

Входной файл (e.in) Выходной файл (e.out)
1
5 2
4 1 2 3 4
2 5 3
3 1
0
2
5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
2
3
10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
1
4
4 2
2 1 2
2 3 4
1 3
-1

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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


1.590s 0.017s 79