题意：按要求操作集合
思路：并查集，因为我们一般都为i的祖先设为自己，但是当我们移动某个数字的时候，这个数字可能是这个集合的祖先，这会冲突，所以我们将i的祖先设为i+n
#include#include #include #include 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; }