絕對有一種更簡單的方法:忘掉所有的節點業務。節點只是概念上的,不需要從字面上實現它們,而且更容易。
所有你需要的是兩個整數數組。一個存儲父母和一個存儲隊伍的人。所以在一種僞代碼中,它看起來像這樣:
disjoint_set {
int[] parent, rank;
makeset(int n)
{
rank = new int[n];
parent = new int[n];
for(int i = 0; i < n; i++)
parent[i] = i;
}
int find(int i)
{
if (parent[i] != i)
parent[i] = find(parent[i]);
return parent[i];
}
void union(int x, int y)
{
x_root = find(x);
y_root = find(y);
if (x_root != y_root) {
if (rank[x_root] < rank[y_root])
parent[x_root] = y_root;
else if (rank[x_root] > rank[y_root])
parent[y_root] = x_root;
else {
parent[y_root] = x_root;
rank[x_root]++;
}
}
}
}