首页 > 代码库 > UVA - 11987 Almost Union-Find[并查集 删除]
UVA - 11987 Almost Union-Find[并查集 删除]
| UVA - 11987 Almost Union-Find |
I hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identical.
The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:
1pq | Union the sets containing p and q. If p and q are already in the same set, ignore this command. |
2pq | Move p to the set containing q. If p and q are already in the same set, ignore this command. |
3p | Return the number of elements and the sum of elements in the set contain- ing p. |
Initially, the collection contains n sets: {1}, {2}, {3}, . . . , {n}. Input
There are several test cases. Each test case begins with a line containing two integers n and m (1 ≤ n, m ≤ 100, 000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1 ≤ p, q ≤ n. The input is terminated by end-of-file (EOF).
Output
For each type-3 command, output 2 integers: the number of elements and the sum of elements.
Explanation
Initially: {1}, {2}, {3}, {4}, {5}
Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}
Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced whentaking out 3 from {3})
Collection after operation 1 3 5: {1,2}, {3,4,5}
Collection after operation 2 4 1: {1,2,4}, {3,5}
Sample Input
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
Sample Output
3 123728
明天再更
//// main.cpp// uva11987//// Created by Candy on 10/12/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>using namespace std;const int N=1e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,op,p,q;int fa[N],sum[N],id[N],cnt[N],num=0;inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}inline void unn(int x,int y){ int f1=find(id[x]),f2=find(id[y]); if(f1!=f2){ fa[f1]=f2; sum[f2]+=sum[f1]; cnt[f2]+=cnt[f1]; }}inline void move(int x,int y){ int f1=find(id[x]),f2=find(id[y]); if(f1!=f2){ sum[f1]-=x; cnt[f1]--; id[x]=++num; sum[f2]+=x; cnt[f2]++; fa[id[x]]=f2; }}int main(int argc, const char * argv[]) { while(scanf("%d%d",&n,&m)!=EOF){ num=n; for(int i=1;i<=n;i++) {fa[i]=sum[i]=id[i]=i;cnt[i]=1;} for(int i=1;i<=m;i++){ op=read(); if(op==1){ p=read();q=read(); unn(p,q); }else if(op==2){ p=read();q=read(); move(p,q); }else{ p=read(); p=find(id[p]); printf("%d %d\n",cnt[p],sum[p]); } } } return 0;}
UVA - 11987 Almost Union-Find[并查集 删除]