并查集
?#include?<?stdio.h?>?
#include?<?memory.h?>?
?const???int??MAX??=???100000?;
?class??UnionFindSet
??{
?public?:
?????int??parent[MAX];
????UnionFindSet();
?????int?????Union(?int??x,??int??y);
?????int??Find(?int??i);
}?;
UnionFindSet::UnionFindSet()
??{
????memset(parent,?-?1?,?sizeof?(parent));
}?
?int?????UnionFindSet::Union(?int??x,??int??y)
??{
????x??=??Find(x);
????y??=??Find(y);
?????//??找出的根節(jié)點(diǎn)x,parent[x]中保存的是根為x的元素的個(gè)數(shù)的相反數(shù);?
??????int??temp??=??parent[x]??+??parent[y];
?????if?(parent[x]??<=??parent[y])
??????{
????????parent[y]??=??x;
????????parent[x]??=??temp;
????}?
??????else??{
????????parent[x]??=??y;
????????parent[y]??=??temp;
????}?
?????return???0?;
}?
?int??UnionFindSet::?Find(?int??i)
??{
?????if?(parent[i]??<???0?)
?????????return??i;
?????else??{
????????parent[i]??=??Find(parent[i]);?//?壓縮路徑;?
??????????return??parent[i];
????}?
}?
??/**/?/*?
int?UnionFindSet::Find(int?x)
{
?????int?i;
?????for(i?=?x;?parent[i]?>=?0;?i?=?parent[i]);//搜索根節(jié)點(diǎn);
?????while(i!=x)//路徑壓縮;
?????{
??????????int?tmp?=?parent[x];
??????????parent[x]?=?i;
??????????x?=?tmp;
?????}
?????return?i;
}
?*/?
?int??main()
??{
?????return???0?;
}?
?