shinasto   4년 전

안녕하세요. 

"사이클의 개수" 문제를 4주 넘게 고민만 하고 있는 초짜 프로그래입니다.

제가 고민하는 부분은 모든 사이클 탐지 방법입니다.

제가 아는 방향 크래프 사이클 탐지 방법은  tarjan algorithm 을 이용한 SCC group으로 묶는 방법입니다.

하지만,,,  이문제에서는 전체 사이클 그룹이 아닌, 개개별의 사이클을 알아야만 사이클 조합을 구할 수 있습니다. (제가 잘못 생각한 것 일수도...)


제가 나름 찾아본 방법은 아래 인도친구가 알려주는 방법이 있는데요..

SCC로 그룹핑 이후 사이클을 탑색하는데,,,, 일단 새부 그룹은 뽑아낼수 있었습니다.
혹시 위 방법이 외 참고할 만한 알고리즘이 있을까요??? 구글신을 통해도 도통 찾기가 어려네요.

고수님들... 부탁드립니다.

koosaga   4년 전

모든 사이클 탐지랑은 상관이 없을 겁니다. 정말 모든 사이클을 저런 식으로 다 탐지하고 싶으시다면 4중 for 문으로도 충분하니까요. 더 빠른 알고리즘이 필요합니다.

shinasto   4년 전

모든 사이클 탐지와 상관없다... 

답변 감사드립니다.  : )   좀더 고민해 보겠습니다 ~~

koosaga   4년 전

아 문제를 헷갈렸네요. 4중 루프랑은 상관이 없겠군요...

여전히 모든 사이클을 다 찾는 식으로 하면 TLE가 날 것입니다. 

댓글을 작성하려면 로그인해야 합니다.