高級數據結構—并查集

原理：參考趣學數據結構

代碼：

#include<stdio.h> #include<stdlib.h> #define N 100 int father[N]; int find(int x) {//尋找共同祖先if (x != father[x]) {father[x] = find(father[x]);}return father[x];//找到了祖先是自己,不能是x自己，一定是x的祖先 } void merge(int x1, int x2) {//將二個有關系的結點合并，時間復雜度為O(2elogn)int p = find(x1);int q = find(x2);//先查找祖先if (p == q) {return ;}else if (p > q) {//合并到祖先小的father[x1] = q;}else {father[x2] = p;}return; } int main() {printf("輸入元素的個數:");int n;scanf_s("%d",&n);for (int i = 1; i <=n; i++) {father[i] = i;}int e1, e2;printf("輸入有關系的元素對:\n");int eNumber;scanf_s("%d", &eNumber);for (int i = 0; i < eNumber; i++) {scanf_s("%d%d", &e1, &e2);merge(e1, e2);}printf("判斷二個人是否有親戚關系:\n");scanf_s("%d%d", &e1, &e2);int p = find(e1), q = find(e2);if (p == q) {printf("%d和%d二個人有親戚關系:\n",e1,e2);}else {printf("%d和%d二個人沒有親戚關系:\n", e1, e2);}system("pause");return 0; }

測試截圖：

時間復雜度O(elogn)，空間復雜度O(1)

如果存在什么問題，歡迎批評指正！謝謝！

總結

以上是生活随笔為你收集整理的高级数据结构---并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。