并查集
- 并查集指的是在一個(gè)集合中的兩種操作：并和查稠屠；
- 并：將集合 S 中的兩個(gè)子集 S1 和 S2 合并卵洗；S1 和 S2 是沒有交集的；
- 查：查看集合 S 中的元素 a 是否在 S 的一個(gè)子集中；
- 并查集的初始狀態(tài)：每個(gè)元素構(gòu)成一個(gè)集合锁孟，所有集合之間是不相交的裸卫；
并查集涉及 2 個(gè)操作
- void unionElements(int p, int q) - 并
- 將元素 p 和元素 q 所在的集合合并成一個(gè)集合仿贬；
- p 和 q 指的是元素在并查集中的位置，p 和 q 指的元素具體是什么并不是并查集關(guān)心的墓贿，并查集關(guān)心 p 和 q 指向的元素是不是在同一個(gè)集合茧泪；
- boolean isConnected(int p, int q) - 查
- 判斷 p 和 q 指向的元素是否在同一個(gè)集合；
public interface UF {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
