并查集及其优化

1.并查集

#define SIZE 100
int UFSets[SIZE];void Initial(int S[]) {for (int i = 0; i < SIZE; i++)S[i]=-1;
}int Find(int S[], int x) {//查while(S[x] >= 0)x = S[x];return x;
}void Union(int S[], int Root1, int Root2) {//并if(Root1 == Root2)return;S[Root2] = Root1;
}

Find操作最坏时间复杂度：O(n)
Union操作最坏时间复杂度：O(1)
优化Union操作，小树并入大树，减少Find操作的复杂度。

2.优化

void Union(int S[], int Root1, int Root2) {if(Root1 == Root2)return;if(Root2 > Root1) {S[Root1] += S[Root2];S[Root2] = Root1;}else {S[Root2] += S[Root1];S[Root1] = Root2;}
}

Find操作最坏时间复杂度：O(logn)

2.进一步优化：压缩路径

优化Find操作，使树更矮。

int Find(int S[], int x) {int root = x;while(S[x] >= 0)root = S[root];while(x != root) {int t = S[x];S[x] = root;x = t;}return root;
}

Find操作最坏时间复杂度：O(α(n))