Задача 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 определяется как последовательность вершин 〈 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 существует либо полностью зеленый, либо полностью красный путь, состоящий из не более, чем двух ребер.

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

Условие

Рассмотрим граф 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).

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

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

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

Условие

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

Поиск в глубину (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|), то есть линейно. За меньшее время мы не успеем даже прочесть все вершины и ребра.

Разбор задач тренировочного турнира.

Задача 4. Лекция. Графы. 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.

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

Задача 5. Лекция. Графы. 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;

Задача 6. Лекция. Графы. Компоненты сильной связности ≡

Условие

Связность для ориентированных графов

Что означает связность для ориентированного графа? Тут надо быть аккуратным. Несвязный неориентированный граф можно разбить на связные компоненты, не соединенные друг с другом. С ориентированными графами ситуация сложнее. Граф на рис. 1 нельзя разбить на две части, не соединенные друг с другом. Но мы не будем называть этот граф связным, поскольку в нем нет пути из G в B или из F в A. Дадим такое определение:

Вершины u и v ориентированного графа называются связанными (connected), если в нем есть путь из u в v, а также путь из v в u.

Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.

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

Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).

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

Свойство 1. Процедура Explore, вызванная для вершины u, заканчивает работу, когда посещены все вершины, достижимые из u.

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

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

Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке

Свойство 2. Вершина, которой поиск в глубину присваивает максимальное tout-значение, лежит в компоненте-истоке.

Свойство 3. Пусть C и C′ — компоненты сильной связности графа и в графе есть ориентированное ребро из C в C′. Тогда максимальное tout-значение вершин в C больше, чем максимальное tout-значение вершин в C′.

Доказательство. Дождемся момента, когда при поиске в глубину впервые появится вершина v из C или C′. Если v ∈ C, то вызов Explore(v) не завершится, пока не будут обработаны все вершины обеих компонент (по свойству 1). Поэтому tout[v] будет больше, чем у всех вершин из C′. Если же v ∈ C′, то вызов Explore(v) обойдет все вершины C′, но до C дело еще не дойдет — и максимальное tout-значение в C тоже будет больше.

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

Таким образом, мы научились находить компоненту-исток и вершину в ней. Как найти все вершины только данной компоненты? Рассмотрим обращенный граф G^R, получаемый из G изменением направлений всех ребер (см. рис. 2). В G^R будут те же компоненты сильной связности, как и у G (покажите). Также, найденная вершина компоненты-истока G будет вершиной компоненты-стока графа G^R. Тогда вызов Explore из найденной вершины на графе G^R обойдет только вершины компоненты истока графа G.

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

Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.

Итак, мы построили следующий алгоритм выделения компонент сильной связности:

1. Запустить обход в глубину графа G, который вернет вершины в порядке убывания tout. Заметим, что для этого достаточно добавлять вершину в массив при выходе Explore из этой вершины.
2. Построить обращенный граф G^R. Запустить процедуру Explore из каждой непосещённой вершины в порядке убывания tout-значений. Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.

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

Условие

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

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

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

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

• 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

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

Условие

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

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

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

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

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

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

Ограничения

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

3 1
2 3

2

Задача C. КПК ≡

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

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

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

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

Ограничения

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

3 1
2 3

1
2 3
1
1 2

Задача D. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача E. Производство деталей ≡

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

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

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

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

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

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

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

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

9 3
3 2 1

Problem F. 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

Задача G. Дайте мне справку, что вам нужна справка... ≡

Условие

Администрация одного города состоит из N чиновников, выдающих справки. Для выдачи справок некоторые из чиновников могут потребовать справок от других чиновников, а те, в свою очередь, от третьих и т.д.

Требуется написать программу, выдающую способ получения справки от M-го чиновника, требующий минимального общего количества справок.

Рекомендуется рассмотреть частичные решения для следующих случаев

• Администрация состоит из одного или двух чиновников.
• Бюрократия в администрации отсутствует — все чиновники выдают справки, ничего не требуя предъявлять.

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

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

Ограничения

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

1 1
0

1 1

2 1
1 2
1 1

0

2 1
1 2
0

2 2 1

Задача H. Конденсация графа ≡

Условие

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

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

Ограничения

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

6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4

2
1 1 1 2 2 2

Задача I. Рекурсия ≡

Условие

"Чтобы понять рекурсию, надо понять рекурсию"

Фольклор

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

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

Рекурсия является очень "мощным" методом построения алгоритмов, но таит в себе некоторые опасности. Например, неаккуратно написанная рекурсивная процедура может войти в бесконечную рекурсию, то есть, никогда не закончить свое выполнение (на самом деле, выполнение закончится с переполнением стека).

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

Рассмотрим программу, состоящую из n процедур P₁, P₂, ..., P_n. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q₀, Q₁, ..., Q_k, что Q₀ = Q_k = P и для i = 1… k−1 процедура Q_i−1 может вызвать процедуру Q_i. В этом случае задача будет заключаться в определении для каждой из заданных процедур, является ли она потенциально рекурсивной.

Требуется написать программу, которая позволит решить названную задачу.

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

Первая строка входного файла содержит целое число n - количество процедур в программе.

Далее следуют n блоков, описывающих процедуры. Блоки отделены друг от друга и от первой строки входного файла строками, каждая из которых содержит по 5 символов "*" (ASCII 42).

Описание процедуры начинается со строки, содержащий ее идентификатор. Далее идет строка, содержащая число k - количество процедур, которые могут быть вызваны описываемой процедурой. Последующие k строк содержат идентификаторы этих процедур — по одному идентификатору на строке.

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

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

Для каждой процедуры, присутствующей во входном файле, необходимо вывести слово YES, если она является потенциально рекурсивной, и слово NO — в противном случае.

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

Ограничения

1 ≤ n ≤ 100

Идентификатор процедуры состоит только из маленьких букв латинского алфавита и цифр. Также идентификатор не пуст, и его длина не превосходит 100 символов.

k ≤ n

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

3
p1
2
p1
p2
*****
p2
1 
p1
*****
p3
1
p1

p1: YES
p2: YES
p3: NO