![][1] Люди встречаются, люди ссорятся, добавляются и удаляют друзей в социальных сетях. Этот пост о математике и алгоритмах, красивой теории, любви и ненависти в этом непостоянном мире. Этот пост о поиске компонент связности в динамических графах. Большой мир генерирует большие данные. Вот и на нашу голову свалился большой граф. Настолько большой, что мы можем удержать в памяти его вершины, но не ребра. Кроме того, относительно графа приходят обновления – какое ребро добавить, какое удалить. Можно сказать, что каждое такое обновление мы видим в первый и последний раз. В таких условиях необходимо найти компоненты связности. Поиск в глубину/ширину здесь не пройдут просто потому, что весь граф в памяти не удержать. Система неперескающихся множеств могла бы сильно помочь, если бы ребра в графе только добавлялись. Что же делать в общем случае? [Кто виноват и что делать][2]

[1]: https://habrastorage.org/files/39c/f3b/938/39cf3b938b5442399e34fb75f359aea8.png
[2]: https://habrahabr.ru/post/276563/#habracut