2016/11/18 Algorithm

今天上課2hrs
結束ch17, 開始ch21 data structure for disjoint set, 這章並不難
應用: 找出connected component

Original Disjoint
Make() => O(1) *n
Find()  => O(1) *f
Union() =>worst O(n) *(n-1)
=>worst O(n^2)

Weighted Disjoint
Make() => O(1) *n
Find()  => O(1) *f
Union() =>O(nlgn)
=>worst O(m+nlgn)
where m=n+f+(n-1), n:#Make f:#Find, m: #(Make,Find,Union)