classDisjointset definitialize(n) @set=(0..n).to_a @cnt=n; end defgetroot(i) i=@set[i]whilei!=@set[i] returni end defsame?(i,j) getroot(i)==getroot(j) end defunion(i,j) @cnt-=1 b=getroot(j) i,@set[i]=@set[i],bwhile@set[i]!=b j,@set[j]=@set[j],bwhile@set[j]!=b end attr_reader:cnt end
어떤 두 원소가 같은 그룹에 속해 있는지 알아낼 수 있고, 빠른 시간에 그룹을 결합할 수 있는 자료구조인 서로소 집합입니다. Kruskal 등의 알고리즘을 구현할 때 많이 쓰입니다.
이올린에 북마크하기
이올린에 추천하기