推 babyghost:推, 寫的真詳細. 03/23 15:30
→ babyghost:我以前實作的 code, 參考 DS in C++ 實作版 XD 03/23 15:31
推 cplusplus:一班的UNION用這種做法再加上一點小技巧 可以答到O(1)的 03/24 00:47
→ cplusplus:操作(每種操作 amortised analysis) 03/24 00:48
→ cplusplus:說錯 是set的操作 不是union的操作 03/24 00:51
其實單純要維持集合關係也可以用ary
以原po的7個node來說
開一個size為8的ary
index=0~7 0不用(方便表示而已 囧)
然後把i=0~7令a[i]=i; //表示指到自己 也就是代表自己是root
現在假設{1,3,6}在同一個set
那就把3跟6的內容改成1
這樣在找3的root時候看到a[3]內容是1 就知道3上面有1
然後再看a[1]的內容 這時候a[1]的內容是1 表示node_1是3的root
圖:
1
↗ ↖
3 6
實際:
index 0 1 2 3 4 5 6 7
value 0 1 2 1 4 5 1 7
再假設{2,5}在同一個set
那就是a[5]=2;
圖:
2
↗
5
實際:
index 0 1 2 3 4 5 6 7
value 0 1 2 1 4 2 1 7
好啦 現在有4個set分別是{1,3,6},{2,5},{4},{7}
假設下一個要檢查的邊是(6,1)
那從6去往上trace會找到1 從1往上trace也會找到1
所以1跟6是在同一個set中
接下來假設要檢查的邊是(2,3)
從3往上trace會找到1
從2往上trace會找到2
因為兩個找到不同的root 所以是在不同的set中
那就可以把這個edge加入 然後把兩個set做聯集
聯集的作法就是a[2]=1就好了
圖:
1
↗↑↖
2 3 6
↗
5
實際:
index 0 1 2 3 4 5 6 7
value 0 1 1 1 4 2 1 7
一般化的話就是find(a,b)
a,b分別一路找到自己的root 假設為p,q
若p==q 則a,b在同一set
若p!=q 則a,b在不同set 可將E(G)=(a,b)加入 然後令a[q]=p
我自己是覺得這樣做好像也可以@@"
--
有錯請指正<(_ _)>
--
ˋ(′～‵")ˊ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.208.248