Как найти количество ребер в конденсации графа

Как найти количество ребер в конденсации графа

Графы, DFS, MST

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

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные

В первой строке входного файла даны два натуральных числа N и M (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, вывести -1.

Примеры

входные данные

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

выходные данные

Решение

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Дан неориентированный граф, не обязательно связный, но не содержащий петель и кратных рёбер. Требуется найти все мосты в нём.

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количества вершин и рёбер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).

Следующие m строк содержат описание рёбер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).

Выходные данные

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

Примеры

входные данные

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

выходные данные

Решение

C. Точки сочленения

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Дан неориентированный граф. Требуется найти все точки сочленения в нём.

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количества вершин и рёбер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).

Следующие m строк содержат описание рёбер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).

Выходные данные

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

Примеры

входные данные

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

выходные данные

Решение

D. Компоненты реберной двусвязности

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

Компонентой реберной двусвязности графа 〈 V,E 〉 называется подмножество вершин S ⊂ V, такое что для любых различных u и v из этого множества существует не менее двух реберно не пересекающихся путей из u в v.

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

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (1  ≤  n  ≤  20 000, 1  ≤  m  ≤  200 000).

Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).

Выходные данные

В первой строке выходного файла выведите целое число k — количество компонент реберной двусвязности графа. Во второй строке выведите n натуральных чисел a1, a2, …, an, не превосходящих k, где ai — номер компоненты реберной двусвязности, которой принадлежит i-я вершина.

Примеры

входные данные

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

выходные данные

Решение

E. Компоненты вершинной двусвязности

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

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

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

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).

Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).

Выходные данные

В первой строке выходного файла выведите целое число k — количество компонент вершинной двусвязности графа. Во второй строке выведите m натуральных чисел a1, a2, …, am, не превосходящих k, где ai — номер компоненты вершинной двусвязности, которой принадлежит i-е ребро. Ребра нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Примеры

входные данные

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

выходные данные

Решение

F. Конденсация графа

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Требуется найти количество ребер в конденсации ориентированного графа. Примечание: конденсация графа не содержит кратных ребер.

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно (n ≤ 10 000,  m ≤ 100 000). Следующие m строк содержат описание ребер, по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — началом и концом ребра соответственно (1  ≤  bi,  ei  ≤  n). В графе могут присутствовать кратные ребра и петли.

Выходные данные

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

Примеры

входные данные

выходные данные

Решение

G. Планирование вечеринки

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 512 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Петя планирует вечеринку, это дело непростое. Одна из главных проблем в том, что некоторые его друзья плохо ладят друг с другом, а некоторые — наоборот. В результате у него есть множество требований, например: «Я приду только если придет Гена» или «Если там будет Марина, то меня там точно не будет».

Петя формализовал все требования в следующем виде: «[+-]name1 => [+-]name2», здесь «name1» и «name2» — имена двух друзей Пети, «+» означает, что друг придет в гости, «-» — что не придет. Например, выражение «Если Андрея не будет, то Даша не придет» записывается так: «-andrey => -dasha».

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

Входные данные

В первой строке входного файла записаны числа n и m — число друзей Пети и число условий (1 ≤ n, m ≤ 1000). В следующих n строках записаны имена друзей. Имена друзей состоят из маленьких латинских букв и имеют длину не больше 10. В следующих m строках записаны условия.

Выходные данные

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

Примеры

входные данные

3 3
vova
masha
gosha
-vova => -masha
-masha => +gosha
+gosha => +vova

выходные данные

входные данные

выходные данные

входные данные

2 4
vova
masha
+vova => +masha
+masha => -vova
-vova => -masha
-masha => +vova

выходные данные

Решение

H. Авиаперелеты

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: avia.in

вывод: avia.out

Главного конструктора Петю попросили разработать новую модель самолета для компании «Air Бубундия». Оказалось, что самая сложная часть заключается в подборе оптимального размера топливного бака.

Главный картограф «Air Бубундия» Вася составил подробную карту Бубундии. На этой карте он отметил расход топлива для перелета между каждой парой городов.

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

Входные данные

Первая строка входного файла содержит натуральное число n (1 ≤ n ≤ 1000) — число городов в Бубундии.

Далее идут n строк по n чисел каждая. j-ое число в i-ой строке равно расходу топлива при перелете из i-ого города в j-ый. Все числа не меньше нуля и меньше 10^9. Гарантируется, что для любого i в i-ой строчке i-ое число равно нулю.

Выходные данные

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

Примеры

входные данные

4
0 10 12 16
11 0 8 9
10 13 0 22
13 10 17 0

выходные данные

Решение

I. Остовное дерево

ограничение по времени на тест: 4 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

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

Входные данные

Первая строка входного файла содержит натуральное число n — количество вершин графа (1 ≤ n ≤ 10 000). Каждая из следующих n строк содержит два целых числа xi, yi — координаты i-й вершины ( - 10 000 ≤ xi, yi ≤ 10 000). Никакие две точки не совпадают.

Выходные данные

Первая строка выходного файла должна содержать одно вещественное число — вес минимального остовного дерева.

Примеры

входные данные

выходные данные

Решение

J. Остовное дерево 2

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Требуется найти в связном графе остовное дерево минимального веса.

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 100 000). n ≤ 200 000, m ≤ 200 000.

Граф является связным.

Выходные данные

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

Примеры

входные данные

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

выходные данные

Решение

K. Алгоритм двух китайцев

ограничение по времени на тест: 6 секунд

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Вам дан взвешенный ориентированный граф, содержащий n вершин и m рёбер. Найдите минимально возможную сумму весов n - 1 ребра, которые нужно оставить в графе, чтобы из вершины с номером 1 по этим ребрам можно было добраться до любой другой вершины.

Входные данные

В первой строке даны два целых числа n и m (1 ≤ n ≤ 1 000, 0 ≤ m ≤ 10 000) — количество вершин и ребер в графе.

В следующих m строках даны ребра графа. Ребро описывается тройкой чисел ai, bi и wi (1 ≤ ai, bi ≤ n;  - 10^9 ≤ wi ≤ 10^9) — номер вершины, из которой исходит ребро, номер вершины, в которую входит ребро, и вес ребра.

Выходные данные

Если нельзя оставить подмножество ребер так, чтобы из вершины с номером 1 можно было добраться до любой другой, в единственной строке выведите «NO».

Иначе, в первой строке выведите «YES», а во второй строке выведите минимальную возможную сумму весов ребер, которых необходимо оставить.

Примеры

входные данные

выходные данные

входные данные

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

выходные данные

Решение

Источник

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

Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.

Понятно, что такое отношение транзитивно: если $a$ и $b$ сильно связны, и $b$ и $c$ сильно связны, то $a$ и $c$ тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.

Граф с тремя компонентами сильной связности

Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.

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

#Конденсация графа

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

Лемма. Запустим dfs. Пусть $A$ и $B$ — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро $A to B$. Тогда:

$$
maxlimits_{a in A}(tout_a) > maxlimits_{bin B}(tout_b)
$$

Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.

Пусть первой была достигнута компонента $A$, то есть в какой-то момент времени dfs заходит в некоторую вершину $v$ компоненты $A$, и при этом все остальные вершины компонент $A$ и $B$ ещё не посещены. Но так как по условию в графе конденсаций есть ребро $A to B$, то из вершины $v$ будет достижима не только вся компонента $A$, но и вся компонента $B$. Это означает, что при запуске из вершины $v$ обход в глубину пройдёт по всем вершинам компонент $A$ и $B$, а, значит, они станут потомками по отношению к $v$ в дереве обхода, и для любой вершины $u in A cup B, u ne v$ будет выполнено $tout_v] > tout_u$, что и утверждалось.

Второй случай проще: из $B$ по условию нельзя дойти до $A$, а значит, если первой была достигнута $B$, то dfs выйдет из всех её вершин ещё до того, как войти в $A$.

Из этого факта следует первая часть решения. Отсортируем вершины по убыванию времени выхода (как бы сделаем топологическую сортировку, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины в сортировке. В эту компоненту точно не входят никакие рёбра из других компонент — иначе нарушилось бы условие леммы, ведь у первой вершины $tout$ максимальный. Поэтому, если развернуть все рёбра в графе, то из этой вершины будет достижима своя компонента сильной связности $C^prime$, и больше ничего — если в исходном графе не было рёбер из других компонент, то в транспонированном не будет ребер в другие компоненты.

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

vector<int> g[maxn], t[maxn];
vector<int> order;
bool used[maxn];
int component[maxn];
int cnt_components = 0;

// топологическая сортировка
void dfs1(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) 
            dfs1(u);
    order.push_back(v);
}

// маркировка компонент сильной связности
void dfs2(int v) {
    component[v] = cnt_components;
    for (int u : t[v])
        if (component[u] == 0)
            dfs2(u);
}


// в содержательной части main:

// транспонируем граф
for (int v = 0; v < n; v++)
    for (int u : g[v])
        t[u].push_back(v);

// запускаем топологическую сортировку
for (int i = 0; i < n; i++)
    if (!used[i])
        dfs1(i);

// выделяем компоненты
reverse(order.begin(), order.end());
for (int v : order)
    if (component[v] == 0)
        dfs2(v), cnt_components++;

TL;DR:

  1. Сортируем вершины в порядке убывания времени выхода.
  2. Проходимся по массиву вершин в этом порядке, и для ещё не помеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компоненты связности.

После этого номера компонент связности будут топологически отсортированы.

Источник

  1. /*! Задача 3D. Condense 2. Конденсация графа [1 sec, 256 mb]

  2.  *

  3.  * Требуется найти количество ребер в конденсации ориентированного графа.

  4.  * Примечание: конденсация графа не содержит кратных ребер.

  5.  *

  6.  * Формат входных данных

  7.  * Первая строка входного файла содержит два натуральных числа n и m — количество

  8.  * вершин и ребер графа соответственно (n <= 10 000, m <= 100 000).

  9.  * Следующие m строк содержат описание ребер, по одному на строке.

  10.  * Ребро номер i описывается двумя натуральными числами bi, ei —

  11.  * началом и концом ребра соответственно (1 <= bi, ei <= n).

  12.  * В графе могут присутствовать кратные ребра и петли.

  13.  *

  14.  * Формат выходных данных

  15.  * Первая строка выходного файла должна содержать одно число — количество ребер в

  16.  * конденсации графа.

  17.  *

  18.  *

  19.  */

  20. #include <iostream>

  21. #include <vector>

  22. #include <algorithm>

  23. #include <set>

  25. using namespace std;

  27. void readGraph(int m, vector<vector<int>> &graphList, vector<vector<int>> &trGraphList)

  28. {

  29. int u = 0;

  30. int v = 0;

  31. for (int i = 0; i < m; i++)

  32. {

  33. cin >> u >> v;

  34.         graphList[u – 1].push_back(v – 1); // смещение нумерации на 1 вниз

  35.         trGraphList[v – 1].push_back(u – 1); // транспонированый граф

  36. }

  38. // Вывод графа

  39. //    for (size_t i = 0; i < trGraphList.size(); i++)

  40. //    {

  41. //        cout << i + 1 << ” – “;

  42. //        for (int v : trGraphList[i])

  43. //            cout << v + 1 << ” “;

  44. //        cout << endl;

  45. //    }

  46. }

  48. void dfs1(const int &u, const vector<vector<int>> &graphList, vector<bool> &used, vector<int> &order)

  49. {

  50.     used[u] = true;

  51. for (int v : graphList[u])

  52. {

  53. if (!used[v])

  54.             dfs1(v, graphList, used, order);

  55. }

  56.     order.push_back(u);

  57. }

  59. void dfs2(const int &u, const int &c, const vector<vector<int>> &trGraphList, vector<int> &color, vector<int> &currentComponent)

  60. {

  61.     color[u] = c;

  62.     currentComponent.push_back(u);

  63. for (int v : trGraphList[u])

  64. {

  65. if (color[v] == –1)

  66.             dfs2(v, c, trGraphList, color, currentComponent);

  67. }

  68. }

  71. int main()

  72. {

  73.     ios_base::sync_with_stdio(0);

  74. cin.tie(0);

  76. int n = 0;

  77. int m = 0;

  78. cin >> n >> m;

  79.     vector<vector<int>> graphList(n);

  80.     vector<vector<int>> trGraphList(n);

  81.     readGraph(m, graphList, trGraphList);

  83.     vector<int> order;

  84.     vector<bool> used(n, false);

  85. for (int i = 0; i < n; i++)

  86. if (!used[i])

  87.             dfs1(i, graphList, used, order);

  89.     reverse(begin(order), end(order));

  90. //    cout << “graph order: “;

  91. //    for (int i = 0; i < n; i++)

  92. //        cout << order[i] + 1 << ‘ ‘;

  93. //    cout << endl;

  94.     vector<int> color(n, –1);

  95.     vector<int> currentComponent;

  96.     vector<vector<int>> components;

  97. for (int i = 0, c = 0; i < n; i++, c++)

  98. {

  99. int u = order[i];

  100. if (color[u] == –1)

  101. {

  102.             dfs2(u, c, trGraphList, color, currentComponent);

  103.             components.push_back(currentComponent);

  104.             currentComponent.clear();

  105. }

  106. }

  108.     set<pair<int, int>> s;

  109. for (int u = 0; u < n; u++)

  110. {

  111. for (int v : graphList[u])

  112. {

  113. if (color[u] != color[v])

  114.                 s.insert(make_pair(color[u], color[v]));

  115. }

  116. }

  118. cout << s.size();

  120. return 0;

  121. }

  123. /*

  124. 4 4

  125. 2 1

  126. 3 2

  127. 2 3

  128. 4 3

  130. 2

  131. */

Источник

Добавить комментарий