Тема: Вершины принадлежащие/не принадлежащие циклам
Как за O(N+M) найти в графе все вершины которые принадлежат хотя бы одному циклу в неориентированном графе?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Вершины принадлежащие/не принадлежащие циклам
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Как за O(N+M) найти в графе все вершины которые принадлежат хотя бы одному циклу в неориентированном графе?
Все такие вершины принадлежат компонентам реберной двусвязности размера >=3. А эти компоненты можно легко за О(Н+М) найти.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Вершины принадлежащие/не принадлежащие циклам