Как в DSU быстро узнавать размер компоненты и общее число компонент?
В задаче по ходу добавляю рёбра и после каждого должен выводить размер компоненты, в которой оказалась вершина, и текущее количество компонент связности. Как хранить размеры в DSU, чтобы это было O(α(n)) на запрос, и не сломать объединение по рангу?
2 ответа
Храним размер только в корне компоненты. При объединении прибавляем размер меньшего дерева к большему. Объединять удобно по размеру (union by size) — это альтернатива рангу с теми же гарантиями, и заодно сразу даёт нужное число.
struct DSU {
vector<int> p, sz;
int comps;
DSU(int n) : p(n), sz(n, 1), comps(n) { iota(p.begin(), p.end(), 0); }
int find(int x){ while(x!=p[x]) x=p[x]=p[p[x]]; return x; }
bool unite(int a, int b){
a=find(a); b=find(b);
if(a==b) return false;
if(sz[a] < sz[b]) swap(a,b);
p[b]=a; sz[a]+=sz[b]; --comps; // слили два множества в одно
return true;
}
int size(int x){ return sz[find(x)]; } // размер компоненты
};
Теперь dsu.size(x) — размер компоненты за O(α(n)), а dsu.comps — число компонент за O(1). Каждое успешное unite уменьшает comps на 1. По памяти O(n). Это самый ходовой DSU для офлайн/онлайн задач на связность.
Типичная ошибка: брать sz[a] без find, то есть dsu.sz[x]. Размер валиден только у корня, а у некорневого элемента в sz лежит мусор (старый размер на момент, когда он был корнем). Всегда sz[find(x)]. И ещё: если объединяете по рангу (а не по размеру), массив размеров всё равно держите и обновляйте отдельно — ранг и размер это разные вещи, ранг не равен размеру.