并查集
星期五花了一個(gè)小時(shí)敲完了并查集代碼春哨，花了大部分時(shí)間去調(diào)試結(jié)果發(fā)現(xiàn)問(wèn)題源頭出在eclipse重定向中與我自身代碼并無(wú)關(guān)系熄赡，最后只能命令行運(yùn)行了碗暗。
并查集可能這個(gè)名字很多人很陌生，其實(shí)我本身也是今天第一次聽(tīng)到這個(gè)概念挤茄，其中有幾個(gè)專有名詞分別是：觸點(diǎn)山害、連接纠俭、等價(jià)類、連通分量浪慌≡┚＃可能這么說(shuō)太抽象了，我拿具體的例子來(lái)舉個(gè)例：
金庸寫的小說(shuō)中肯定有正邪兩派之分权纤，那么其中一個(gè)一個(gè)人物我們稱之為觸點(diǎn)钓简，那么為了不與同道中人發(fā)生打斗乌妒，比如喬峰和段譽(yù)這無(wú)論如何打不起來(lái)，因?yàn)樗麄兪前莅炎有值芡獾恕Ｄ敲此麄兊陌莅炎有值苓@個(gè)關(guān)系就是連接的意思撤蚊。
那么怎么等價(jià)類怎么理解呢？
- 自反性：?jiǎn)谭搴蛦谭遄约菏窍噙B的(自己肯定跟自己有關(guān)系损话，為了找出帶頭大哥也是為了自己崇高理想信念)
- 對(duì)稱性：?jiǎn)谭搴投巫u(yù)有關(guān)系侦啸，那么段譽(yù)與喬峰有關(guān)系。
- 傳遞性：?jiǎn)谭搴投巫u(yù)有關(guān)系丧枪，段譽(yù)與虛竹也有關(guān)系光涂，那么喬峰與虛竹也有關(guān)系。
最后這三個(gè)人形成的關(guān)系網(wǎng)算是一個(gè)連通分量（當(dāng)然這是直接與喬峰有關(guān)系）,比如夢(mèng)姑肯定與虛竹有關(guān)系豪诲，所以夢(mèng)姑不可能跟喬峰為敵顶捷，她也處在這個(gè)關(guān)系網(wǎng)內(nèi)。如果我加上阿紫可能關(guān)系會(huì)亂類似于這種情況先排除屎篱。
那么我們來(lái)扯扯快樂(lè)的單身漢鳩摩智，鳩摩智他就是一個(gè)人葵蒂，他前期與段譽(yù)為敵交播，那么基本算是跟那個(gè)連通分量為敵，喬峰看見(jiàn)不降龍十八掌打死他（竟敢欺負(fù)我兄弟践付，雖然我不屑于跟你糾纏）
按以上規(guī)律我們可以用代碼表示
public class UF{
private int[] ids;
private int count;
public UF(int n) {
count = n;
ids = new int[n];
for(int i=0; i<n; i++) {
ids[i]=i;//為了簡(jiǎn)單都是從0到n的
}
}
public int getCount() {
return count;
}
public int find(int p) {
return ids[p];
}
public boolean connect(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int pid = find(p);
int qid = find(q);
for(int i=0;i<ids.length;i++) {
if(pid==ids[i]) ids[i] = qid;
}
count--;
}
}
ids數(shù)組下標(biāo)作為唯一區(qū)分人物的id秦士，那么數(shù)組值代表他們那一個(gè)門派的代表人物比如說(shuō)喬峰是1號(hào)那么ids[虛竹.id]=1，ids[段譽(yù).id]=1永高；(只是個(gè)簡(jiǎn)略版本后期會(huì)優(yōu)化)隧土；
count代表不同派系比如慕容復(fù)有自己一派系、喬峰有自己一個(gè)派系命爬、鳩摩智快樂(lè)的單身漢一派系曹傀。我們?cè)趺摧斎肽兀繑?shù)組大小代表有幾個(gè)人饲宛，然后通過(guò)每一對(duì)之間是否有關(guān)系組成各個(gè)派系皆愉。（大家可以試一試）
