Оффтоп
Вот, кстати,
нашёл задачу, где
dsu не асимптотически, но быстрее. чем
dfs, ну и даже сам код лаконичнее и яснее
Конечно не очень хороший бенчмарк, но leetcode для dsu выдаёт в среднем 150 милисекунд, а для dfs 190 милисекунд, там для dfs, в частности, нужно ещё в список смежности превратить исходный массив, нужна мапа (медленная) для vertex To component, сет для used ну и сам код намного длинее выходит
В общем, dfs не очень работает с матрицей смежности и тем более списком ребёр (как в задаче выше), а только с списком смежности, поэтому если в задаче изначально граф дан не в нужном виде, то лучше использовать dsu, ну и также, чтобы рукам не поддерживать компоненты связности, так как это заложено в dsu. То есть если в ходе работы алгоритма нет чёткой структуры графа, или рёбра вообще появляются налету (находятся по каким-то признакам, а не даны заранее), то как раз через dsu удобно делать unite(from, to) этих рёбер
Вот ещё причину
нашёл 
