1

Тема: Вершины принадлежащие/не принадлежащие циклам

Как за O(N+M) найти в графе все вершины которые принадлежат хотя бы одному циклу в неориентированном графе?

2

Re: Вершины принадлежащие/не принадлежащие циклам

Все такие вершины принадлежат компонентам реберной двусвязности размера >=3. А эти компоненты можно легко за О(Н+М) найти.