kkw564   4년 전

유니온 파인드의 파인드식으로 생각해서 풀었습니다.

우선 사이클이 존재하는지 노드 하나를 잡아서 돌면서 벡터에 현재 노드를 계속 담아줍니다.

그리고 사이클이라면 return값에는 사이클에 참가한 노드의 가 반환되고 노드가 담긴 벡터를 가지고 갑니다. (시작점 - 시작점으로 와야 사이클이라고 판단시켰습니다.) 그게 아닌 경우에는 -1이 리턴됩니다.

이제 retrun값이 -1이 아닌경우 받은 벡터에 있는 노드의 부모들은 -1로 표시하여 더이상 사이클 판단여부에 참여하지 않도록하고 ans에 사이클에 참여한 노드수를 추가했습니다.


어디를 더 줄여야 시간초과를 벗어날 수 있나요?? 84%에서 초과네요


한가지 의구심이 드는 부분이 있는데


1->2->3->4->3->4->3->4인경우

1에서 사이클 탐색을 시작했다면 이때 바로 3->4를 잡을 수 있는 코드가 있어야하나요?

있어야한다면 어떻게 만드는지 힌트좀 주시면 감사하겠습니다.


제 코드는 1에서는 사이클 못잡고, 2에서 못잡고 3에서 잡는 방식이거든요


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