Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
В программе ниже используются массивы:
Old[1…n] – старая или новая (непроверенная) вершина,
NV[1…n] – новый номер вершины,
Low[1…n] – значения функции,
Fath[1…n] – номера вершин-отцов.
Граф задан списками смежных вершин L[1…n].
Подготовка массивов, выделение корней глубинных остовных деревьев (для отдельных компонент связности), вызов рекурсивной функции поиска в глубину:
dcomp = 0; newnum = 0;
for (k = 1; k <= n; k++) {
Old[k] = 0; Fath[k] = 0;
}
for (k = 1; k <= n; k++)
if (Old[k] == 0) search2(k);
Поиск в глубину с выделением двусвязных компонент:
void search2(int v) {
Old[v] = 1; Low[v] = NV[v] = ++newnum;
for (w 
L[v])
if (Old[w] == 0) { // (v, w) - древесное
push(v, w); Fath[w] = v; search2(w);
if (Low[w]>=NV[v]) {dcomp++; //v – ТС
do rib=pop(); добавить(rib, dcomp);
while (rib!= (v, w));
} Low[v] = min(Low[v], Low[w]);
}
else if (NV[w]<NV[v] && w!=Fath[v]) { // обр
push(v, w); Low[v] = min(Low[w], NV[w]);
}
}
Трудоемкость данного алгоритма составляет 
.
Сильно связные компоненты
Задан ориентированный граф 
. Для него могут быть определены компоненты трех типов, в зависимости от условий связности произвольной пары вершин 
и 
, принадлежащих одной компоненте:
1. Слабо связные – из и существует маршрут, если все дуги 
заменить на ребра.
2. Односторонние – существует либо путь из в , либо из в , либо оба вместе.
3. Сильно связные – существуют пути из в и обратно (т. е. цикл, образованный дугами).
Слабо связные компоненты можно найти поиском в глубину на графе, в котором все дуги заменены ребрами.
Односторонние можно выделить с помощью построения и объединения глубинных остовных деревьев со всеми возможными корневыми вершинами.
На множестве вершин 
можно определить отношение эквивалентности: 
пути из в и обратно.
Пусть 
– классы эквивалентности, а 
– множества дуг, соединяющих вершины . Тогда 
– сильно связные компоненты .
1-й алгоритм выделения ССК (1 поиск в глубину, Ахо)
При поиске в глубину на орграфе образуются 4 типа дуг:
1. Древесные.
2. Прямые – от предков к потомкам (не древесные).
3. Обратные – от потомков к предкам.
4. Поперечные – соединяют вершины, не являющиеся предками и потомками друг друга.
(на рисунке: 1 – синие, 2 – зеленые, 3 – красные, 4 – розовые; цифры – номера вершин в порядке обхода в глубину).
 |
Лемма: если 
– поперечная дуга, то 
.
Док-во:
1. ведет в уже пройденную вершину , иначе эта дуга была бы древесной.
2. Если проверяется дуга , то поиск в глубину из вершины пока не закончен (необходимо проверить все возможные пути из ). Пусть была пройдена раньше, чем , т. е. 
. Это возможно только в том случае, когда лежит на некотором пути из (состоящем из древесных дуг), но тогда дуга – прямая.
Основная лемма об ССК (без док-ва, Ахо):
Пусть 
– ССК, а 
– глубинный остовный лес на . Тогда вершины вместе с дугами, входящими в 
, образуют дерево.
Следствие:
- любые вершины 
имеют общего предка;
- предок 
с минимальным номером, присвоенным при поиске, является корнем дерева (и однозначно определяет дерево).
Если перенумеровать в том порядке, в каком для заканчивается поиск в глубину (т. е., сначала 
, затем 
,…), то выполняется следующая
Лемма: 
граф состоит из вершин, являющихся потомками и не принадлежащих ни одному из 
.
Практическое следствие: при поиске в глубину будем помещать вершины в стек в порядке их обхода; при обнаружении корня 
какой-либо ССК вытолкнем из стека все вершины до включительно – все они принадлежат одной ССК.
Каждая вершина принадлежит только одной ССК, но могут существовать дуги, соединяющие вершины из разных ССК.
Рассмотрим ССК 
и , где выделяется раньше, чем .
 |
Варианты соединений:
1. обе дуги – 
и . Невозможен, т. к. в этом случае 
образуют одну ССК.
2. только дуга . Поиск для не закончится, пока не будут проверены все возможные пути из ее вершин, в том числе и включающие дугу . Поэтому не может быть выделена раньше, чем .
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)