유니온 파인드구조가 index 기반이잖아요?
find (1)
union (3,4)
이렇게말고
find (Elem e)
union (Elem u,Elem v)
이렇게 쓰려면 뭐가좋을까요 성능 조금포기하고 stl레드블랙트리인 map에 키를 elem으로하고 데이터를 인덱스로넣고 (차례차례1 2 3 4...)
map에 insert될때 반환된 포인터를 배열에저장
find할시에
Elem e(키)를 index(데이터) 로변환
union은
위에서얻은 index로 포인터배열[index]->data(부모라 생각하시면되용) 로 union 연산
find union모두 logn성능
다른방법이있을까요...
union find는 인덱스(번호)있는 원소만 써야하나요
find(elem.idx)라던지...
find (1)
union (3,4)
이렇게말고
find (Elem e)
union (Elem u,Elem v)
이렇게 쓰려면 뭐가좋을까요 성능 조금포기하고 stl레드블랙트리인 map에 키를 elem으로하고 데이터를 인덱스로넣고 (차례차례1 2 3 4...)
map에 insert될때 반환된 포인터를 배열에저장
find할시에
Elem e(키)를 index(데이터) 로변환
union은
위에서얻은 index로 포인터배열[index]->data(부모라 생각하시면되용) 로 union 연산
find union모두 logn성능
다른방법이있을까요...
union find는 인덱스(번호)있는 원소만 써야하나요
find(elem.idx)라던지...
index기반 유니온파인드가 구현도 굉장히 간단하고 성능도 매우 좋은데 굳이 element 기반으로 하려는지요? 우선 stl의 map컨테이너로 유니온파인드는 구현할수 없습니다. 말씀하신대로 map은 키를 기준으로 정렬을 기본으로 하는 RBTree이기 때문이죠. 굳이 element자체를 파라미터로 받으면서 유니온함수 파인드 함수를 구현하려면 struct element { T data; int rank; element *parent; };로 구현하시면 되겠습니다. 하지만 배열인덱스를 사용하는 구현에 비해서 포인터를 사용하는 구현은 여러모로 느릴텐데요.