find帶壓縮路徑的并查集

int fa[];
void init(int _size)
{for(int i=0;i<=_size;i++){fa[i] = i;}
}
int find(int aim)
{int cur = aim;while (fa[aim] != aim){aim = fa[aim];}while (fa[cur] != cur){int tmp = cur;cur = fa[cur];fa[tmp] = aim;}return aim;
}
void join(int a,int b)
{a = find(a);b = find(b);fa[a] = b;
}

遞歸find

int find(int aim)
{if(fa[aim] == aim)return aim;int fa = find(fa[aim]);//接著深入找return fa[aim] = fa;//最后更新，返回的都是頭子
}//同上
int zuxian(int k){//并查集函數，注意路徑壓縮return f[k]==k?k:f[k]=zuxian(f[k]);
}