Лекция по MST и DSU (25 ноября 2016)

1. DSU на списках за O(m + nlogn) (с доказательством)
2. DSU на ссылках к корню за O((m+n)A^-1(n,m))
3. Алгоритм Краскала (сортировка + DSU)
4. Алгоритм Прима (аналог Дейкстры)
5. Доказываем O(log*n) на запрос для второго из DSU