Давайте посмотрим на эту задачу. (она пока не появилась в архиве.)
А также посмотрим на это её решение.
Первый вопрос, который возник у меня в голове — почему это работает по времени?
Если мы посмотрим на $$$dfs$$$, то заметим, что он перебирает вершины из сета и, если ребра между текущей вершиной и вершиной из сета нет, то переходит в вершину из сета.
Первое что приходит в голову: казалось бы, контрпример строится достаточно просто, т.е. пусть не будет ребра между текущей вершиной и последней сете и так далее, тогда на каждом этапе $$$dfs$$$ мы перебираем в среднем $$$V$$$ вершин и всего заходов в dfs у нас $$$V$$$ => $$$V^2 \cdot $$$ (сложность извлечения и удаления вершин)
Но давайте посмотрим на это с другой стороны: а сколько раз мы НЕ зайдём в наш if и не перейдём дальше? То, что мы не перешли означает, что ребро существует, а каждое ребро мы рассмотрим, очевидно, не более двух раз, из $$$u$$$ и из $$$v$$$, если ребро $$$(u, v)$$$, получается, что мы только $$$2E$$$ раз не перейдём, а также каждый состоявшийся переход сокращает число вершин, которые надо посетить на 1 $$$\Rightarrow$$$ переходов потребуется не более $$$V$$$ $$$\Rightarrow$$$ суммарная сложность не более $$$(V + E) \cdot $$$ (сложность извлечения и удаления вершин), что, в данной, например, реализации $$$(V + E) \cdot log(V)$$$
