常用場合:
圖的使用 給定兩點 構造圖 判斷兩點之間是否連通
初始化
private static void init(int n, int fa[]) {//初始化數組
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
查根節點
private static int find(int x, int fa[]) {//查
if (fa[x] == x) {
return x;
} else {
fa[x] = find(fa[x], fa);
return fa[x];
}
}
将兩點連接配接在一起
private static void merge(int i, int j, int fa[]) {//并
if (fa[find(i, fa)] != find(j, fa))
fa[find(i, fa)] = find(j, fa);
}
參考連結:https://zhuanlan.zhihu.com/p/93647900