UVA - 11987 Almost Union-Find

本文主要是介绍UVA - 11987 Almost Union-Find，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：按要求操作集合

思路：并查集，因为我们一般都为i的祖先设为自己，但是当我们移动某个数字的时候，这个数字可能是这个集合的祖先，这会冲突，所以我们将i的祖先设为i+n

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100010;int n,m,fa[MAXN],sum[MAXN],num[MAXN];void init(){for (int i = 1; i <= n; i++){fa[i] = i+n;fa[i+n] = i+n;sum[i+n] = i;num[i+n] = 1;}
}int find(int x){if (x != fa[x])fa[x] = find(fa[x]);return fa[x];
}int main(){int op,x,y;while (scanf("%d%d",&n,&m) != EOF){init();for (int i = 0; i < m; i++){scanf("%d",&op);if (op == 1){scanf("%d%d",&x,&y);int fx = find(x);int fy = find(y);if (fx != fy){fa[fx] = fy;sum[fy] += sum[fx];num[fy] += num[fx];}}else if (op == 2){scanf("%d%d",&x,&y);int fx = find(x);int fy = find(y);if (fx != fy){fa[x] = fy;sum[fy] += x;sum[fx] -= x;num[fy]++;num[fx]--;}}else {scanf("%d",&x);int fx = find(x);printf("%d %d\n",num[fx],sum[fx]);}}}return 0;
}

这篇关于UVA - 11987 Almost Union-Find的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---