san9407   1년 전

구글링 해보면 second max값이나 이진서치 이용해서 구하던데(lca에서 최대값 구하는 부분에 추가해서)

저는 위에것들 추가도 안했으니 오히려 계산은 적어야할거 같은데

계속 시간초과네요 ㅠㅠ

어디서 시간초과인지 알려주시면 감사하겠습니다!

windflower   1년 전

find()함수가 부모 노드를 하나씩 검사하는 알고리즘이라면 시간복잡도가 O(V)가 되고 따라서 merge()함수도 시간복잡도가 O(V)가 되네요

그래서 main()함수 반복문에서 시간복잡도가 O(VE)가 되서 시간초과가 발생하는 것 같습니다!!

san9407   1년 전

find함수 parent[x] = find(parent[x]) 일경우 O(1)에 근접한거 아니였나요???

windflower   1년 전

tree에서 LCA 알고리즘 사용하였을 때 O(log n)으로 구할 수 있긴 하고 par[][]배열에서 LCA 알고리즘과 비슷한 방식으로 사용하신 것 같긴 한데...

parent배열에서는 이렇다 할 전처리과정이 보이지 않아서요

저 상태라면 부모노드를 2^k만큼 jump해서 찾는 것이 아니고 한칸씩 올라가면서 찾는 것이라 O(V)이 걸리지 않나요?

san9407   1년 전

find함수는 문제가 없어보이는게..

제가 여태까지 저 방식으로 MST문제를 다 푼걸로보아 find함수 문제는 아닌거 같습니다 ㅠㅠ

san9407   1년 전

찾았습니다.

크루스칼 배열크기도 잘못잡고 86번째줄도 오타가 있었네요..

이거 고치고 나니 역시나 WA..

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