Graph is indirected.

Алгоритм

1. На каждой вершине вызываем makeSet(vertex)
2. Для всех рёбер графа вызываем union(vertex1, vertex2) для vertex1 и vertex2, которые это ребро соединяет.
3. Далее с помощью find(x) можем сказать, принадлежат две вершины одной компоненте связности или разным.

Introduction to Algorithms (Fourth Edition) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022)

Но чем это лучше DFS’а?

Если наш граф статичный, то DFS, действительно, сделает это быстрее. Однако если мы добавляем в граф новые элементы, то этот алгоритм будет быстрее, чем каждый раз запускать DFS.