大家好,又见面了,我是你们的朋友全栈君。
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: 1 p q Union the sets containing p and q. If p and q are already in the same set, ignore this command. 2 p q Move p to the set containing q. If p and q are already in the same set, ignore this command. 3 p Return the number of elements and the sum of elements in the set containing 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 when taking 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 12 3 7 2 8
题意是:1~n,n个数,初始每个数独自作为一个集合,然后进行m次操作。操作有三种:1 p q :把 p 所在的集合合并到 q 所在的集合
2 p q :把 p 从 p 的集合中拿出,放到 q 的集合里
3 p :输出 p 所在的集合的元素个数和元素之和
思路:ma[x]=y 代表x在编号为y的集合里,fa[y]=z 代表编号为y的集合与编号为z的集合在同一连通分支(本来也是集合,但都说集合不太好分辨,并查集的部分就说连通分支吧)内(把集合当作个体来并查集),再用两个数组分别记录连通分支 i 内的数字的个数cou和数字的和sum
这样的话对于1操作:fa[fx]=fy(fx是x所在的连通分支,fy是y所在的连通分支),//合并fx和fy
cou[fy]+=cou[fx];
sum[fy]+=sum[fx];
cou[fx]=0; //清空fx
sum[fx]=0;
2操作:cou[fx]–;
cou[fy]++;
sum[fy]+=x;
sum[fx]-=x;
ma[x]=ma[y];
3操作:cou[fx] sum[fx]
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #include <vector> #define Twhile() int T;scanf("%d",&T);while(T--) #define clc(a,b) memset(a,b,sizeof(a)) #define fora(i,a,b) for(i=a;i<b;i++) #define fors(i,a,b) for(i=a;i>b;i--) #define fora2(i,a,b) for(i=a;i<=b;i++) #define fors2(i,a,b) for(i=a;i>=b;i--) #define PI acos(-1.0) #define eps 1e-6 #define INF 0x3f3f3f3f typedef long long LL; typedef long long LD; using namespace std; const int maxn= 100000+11; map<int,int>ma; int cou[maxn],sum[maxn]; int fa[maxn]; int n,m; void init() { ma.clear(); int i; fora2(i,1,n) { fa[i]=i; cou[i]=1; sum[i]=i; ma[i]=i; } } int findx(int x) { if(x==fa[x])return x; return fa[x]=findx(fa[x]); } int main() { int kcase=0; while(~scanf("%d%d",&n,&m)) { init(); while(m--) { int op; scanf("%d",&op); if(op==3) { int x; scanf("%d",&x); int fx=findx(ma[x]); printf("%d %d\n",cou[fx],sum[fx]); continue; } int x,y; scanf("%d%d",&x,&y); int fx=findx(ma[x]),fy=findx(ma[y]); if(fx==fy)continue; if(op==1) { //合并连通分支fx和fy fa[fx]=fy; cou[fy]+=cou[fx]; sum[fy]+=sum[fx]; //清空fx cou[fx]=0; sum[fx]=0; continue; } //把x从集合ma[x]拿出来 sum[fx]-=x; cou[fx]--; //把x放到集合ma[y] ma[x]=ma[y]; cou[fy]++; sum[fy]+=x; } } return 0; }
转载于:https://www.cnblogs.com/107acm/p/9430924.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107379.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...