[일반] 정점 N, 간선 N인 그래프에서 사이클 분리

[익명(211.234)]

https://www.acmicpc.net/problem/24889
트리에서 간선 하나 추가되니 살짝 어질한데 사이클만 어떻게 잘 찾을 수 있을까요? 고인물분들의 아이디어 부탁 드립니다 흑흑ㅜ

[익명(223.62)]

dfs

[익명(211.36)]

dfs 하면서 부모 저장하고 백엣지 찾는 순간 부모 따라 올라가면 됨.

[지피지기(knon0501)]

난 그냥 차수1인 정점부터 하나씩 떼서 나중에 차수2인 애들만 남게 하는 방법이 젤 쉽더라

[익명(223.38)]

ㅋㅋ ㄹㅇ...

[EN_SA(encludingsalt)]

오

[익명(1.216)]

이거다

[익명(211.234)]

아 위상정렬 비슷하게? 천재시네요 ㄱㅅㄱㅅ