并查集模板

int pre[MAXN];
int Find(int pos) {
    if (pre[pos] == pos) // pre是自己，代表為root節(jié)點(diǎn)
        return pos; 
    int r = pos; 
    while (r != pre[r]) // 找到節(jié)點(diǎn)pos的root
        r = pre[r];
    
    // 路徑壓縮
    int i = pos;
    while (i != r) { // 把沿路pos->root沿路的節(jié)點(diǎn)的root的pre
        //全部設(shè)置為root
        int t = pre[i];
        pre[i] = r;
        i = t;
    }
    return r;
}
void Union(int posX, int posY) { // 把兩個節(jié)點(diǎn)的root設(shè)置為同一個
    int rootX = Find(posX), rootY = Find(posY);
    if (rootX != rootY)
        pre[rootX] = rootY;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容