![][1]Речь пойдёт о простой структуре данных — _системе непересекающихся множеств_. Вкратце: даны непересекающиеся множества (например, компоненты связности графа) и по двум элементам x и y можно: 1) узнать, находятся ли x и y в одном множестве; 2) объединить множества, содержащие x и y. Сама структура очень проста в реализации и описывалась много раз в различных местах (например, есть хорошая статья на [хабре][2] и ещё [кое-где][3]). Но это один из тех удивительных алгоритмов, написать который ничего не стоит, а вот разобраться, почему он работает эффективно совсем нелегко. Я постараюсь изложить относительно простое доказательство точной оценки на время работы этой структуры данных, придуманное Зейделем и Шариром в 2005 (оно отличается от того ужаса, который многие могли видеть в других местах). Конечно, сама структура тоже будет описана, а попутно разберёмся причём здесь обратная функция Аккермана, о которой многие знают только, что она оооочень медленно растёт. [Читать дальше →][4]

[1]: https://habrastorage.org/files/35e/6ec/625/35e6ec62557d4301881d8b2aa82610b6.png
[2]: http://habrahabr.ru/post/104772/
[3]: http://e-maxx.ru/algo/dsu
[4]: http://habrahabr.ru/post/266859/#habracut