Система непересекающихся множества

Август 20, 2022

Главная
Информатика
Система непересекающихся множества

Содержание

2. Определение Система непересекающихся множеств - структура данных для эффективной работы с непересекающимися множествами (каждый элемент принадлежит
3. Доступные операции На СНМ, как на любую структуру данных, накладываются ограничения на то, что должна уметь
4. Представление структуры данных Курс по олимпиадной подготовке по информатике и программированию
5. Make_set void make_set(int v) { par[v] = v; } Код описанный выше, на самом деле реализует
6. find_set int find_set(int v) { while (v != par[v]) v = par[v]; return v; } Будем
7. Union_sets void union_sets(int v, int u) { v = find_set(v); u = find_set(u); if (v par[v]
8. Ассоциативные и коммутативные функции Курс по олимпиадной подготовке по информатике и программированию
9. Задача На вход подается граф из n вершин и m ребер. Следом поступает q запросов одного
11. Скачать презентацию

Слайд 2

Определение
Система непересекающихся множеств - структура данных для эффективной работы с непересекающимися

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

Курс по олимпиадной подготовке по информатике и программированию

Слайд 3

Доступные операции
На СНМ, как на любую структуру данных, накладываются ограничения на

то, что должна уметь делать эта структура.
Для СНМ таким операциями являются:
make_set(x) – добавляет новый элемент x, помещая его в новое множество, состоящее из одного него.
union_sets(x, y) – объединяет два указанных множества (множество, в котором находится элемент х, и множество, в котором находится элемент y).
find_set(x) – возвращает, в каком множестве находится указанный элемент x. В общем случае эта операция возвращает представителя множества.

Курс по олимпиадной подготовке по информатике и программированию

Слайд 4

Представление структуры данных

Курс по олимпиадной подготовке по информатике и программированию

Слайд 5

$Make_set void make_set(int v) { par[v] = v; } Код описанный$

Make_set
void make_set(int v)
{
par[v] = v;
}
Код описанный выше, на самом деле реализует

достаточный для нас функционал.
Он создает множество из одного элемента, в котором представителем будет являться сам элемент.
Итоговая сложность одной операции – O(1)

Курс по олимпиадной подготовке по информатике и программированию

Слайд 6

$find_set int find_set(int v) { while (v != par[v]) v =$

find_set
int find_set(int v)
{
while (v != par[v])
v = par[v];
return v;
}
Будем итеративно

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

Курс по олимпиадной подготовке по информатике и программированию

Слайд 7

$Union_sets void union_sets(int v, int u) { v = find_set(v); u$

Union_sets
void union_sets(int v, int u)
{
v = find_set(v);
u = find_set(u);
if (v <

u)
par[v] = u;
else
par[u] = v;
}
Код описанный выше для каждой пары вершин находит их представителя, и “привязывает” одного представителя к другому.
Итоговая сложность одной операции зависит от сложности операции find_set и равна O(n).

Курс по олимпиадной подготовке по информатике и программированию

Слайд 8

Ассоциативные и коммутативные функции

Курс по олимпиадной подготовке по информатике и программированию

Слайд 9

Задача
На вход подается граф из n вершин и m ребер.

Следом поступает q запросов одного из двух типов:
Поступает пара вершин a, b, между которыми необходимо провести ребро.
Поступает пара вершин a, b, для которых необходимо определить, лежат ли они в одной компоненте.

Курс по олимпиадной подготовке по информатике и программированию

Система непересекающихся множества

Содержание

ОпределениеСистема непересекающихся множеств - структура данных для эффективной работы с непересекающимися

Доступные операцииНа СНМ, как на любую структуру данных, накладываются ограничения на

Представление структуры данных Курс по олимпиадной подготовке по информатике и программированию

Make_setvoid make_set(int v){ par[v] = v;}Код описанный выше, на самом деле реализует

find_setint find_set(int v){ while (v != par[v]) v = par[v];return v;}Будем итеративно

Union_setsvoid union_sets(int v, int u){ v = find_set(v); u = find_set(u); if (v <

Ассоциативные и коммутативные функции Курс по олимпиадной подготовке по информатике и программированию

Задача На вход подается граф из n вершин и m ребер.

Похожие презентации

Определение
Система непересекающихся множеств - структура данных для эффективной работы с непересекающимися

Доступные операции
На СНМ, как на любую структуру данных, накладываются ограничения на

Представление структуры данных

Курс по олимпиадной подготовке по информатике и программированию

Make_set
void make_set(int v)
{
par[v] = v;
}
Код описанный выше, на самом деле реализует

find_set
int find_set(int v)
{
while (v != par[v])
v = par[v];
return v;
}
Будем итеративно

Union_sets
void union_sets(int v, int u)
{
v = find_set(v);
u = find_set(u);
if (v <

Ассоциативные и коммутативные функции

Курс по олимпиадной подготовке по информатике и программированию

Задача
На вход подается граф из n вершин и m ребер.