74
правки
Изменения
Нет описания правки
Во-первых <tex>dfs</tex> работает О (n).
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных <tex>n</tex> затрачивают <tex>О (n)</tex> операций.
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n</tex> выполняется за <tex>О (1)</tex>. Итоговая асимптотика получается <tex>\mathrm{O (n + m)}</tex>, но при достаточно больших <tex>m</tex> ответ за <tex>О (1)</tex> на один запрос.
