알고리즘을 먼저 설명해 주세요.

보통 visit는 방문하지 않은 노드는 0, 방문한 노드는 1로 해서 거르는 게 일반적입니다.

그리고.. 굳이 vector에 push_back하고, size를 구하고.. clear를 할 필요가 있을까요??

배열로 스택 같은 걸 구현하시고, dfs를 새로 수행할 때마다

포인터를 0으로 돌려놓으면 clear 효과를 매우 쉽게 낼 수 있습니다.

visit또한 memset을 안하기위해 각 테스트케이스마다 ++를해주어서 visit를 구분해주고있습니다

그러면 vector부분을 제외하고는 알고리즘 자체는 맞는건가요?

알고리즘은 다음과 같습니다

----

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

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

사이클 탐색을 1번부터 하면서 1->2->3->4->5->4 처럼 도중에 사이클이 발견되면

사이클 크기 2짜리가 있음을 반환하면서 6부터 시작하는 이러한 방식을 이용했습니다.

---

알고리즘 자체는..

어느 노드에서부터 탐색했는가?

만약 부모가 같은 노드들을 만나면 사이클이 있다.

이 두 아이디어를 떠올리면 됩니다. 거의 다 오신 거 같습니다.

어떻게 보면 집합의 find(); 와도 비슷해 보입니다. 만..

다른 것은 dfs를 처음 호출할 때, 부모가 결정된다는 것 정도가 되겠지요?

그렇기 때문에 잘 짜신다면 부모를 찾는 것도 O(1)이 될 거고요.

다만, 이게 잡다한 optimize를 적용하고도 700ms가 넘어가는 걸 보면..

데이터가 빡센 게 들어오는 듯 싶네요. 그 경우에는

함수 몇 개만 잘못 써도.. 시간 초과가 나기 딱 좋겠지요..

약간의 optimize도 요구하는 문제 같습니다.

역시 최적화를 조금 더 해 봐야겠군요..  감사합니다 또 궁금한게 생긴다면 가희님 아이디에 바로 뜰 수 있게 댓글로 질문드릴게요!! ㅋㅋ

감사합니다 문제에대해 생각해주셔서 ㅎㅎ