首页 > 代码库 > [luoguP2342] 叠积木（并查集）

[luoguP2342] 叠积木（并查集）

2024-10-06 16:41:39   209人阅读

传送门

 

up[i] 表示一个木块上面有多少个

all[i] 表示整个连通块内有多少个

那么 一个木块下面的木块个数为 all[root[i]] - up[i] - 1

注意：up[i] 可以在 find 函数中维护，而 all[i] 不好维护，那么我们只需要祖先节点的 all[i] 表示整个连通块内木块的数目即可

　　　合并时也注意维护

 

——代码

技术分享
 1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4  5 int n; 6 int f[N], up[N], all[N]; 7  8 inline int read() 9 {10     int x = 0, f = 1;11     char ch = getchar();12     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14     return x * f;15 }16 17 inline int find(int x)18 {19     if(x ^ f[x])20     {21         int fx = f[x];22         f[x] = find(f[x]);23         up[x] += up[fx];24     }25     return f[x];26 }27 28 int main()29 {30     int i, x, y, fx, fy;31     char s[1];32     n = read();33     for(i = 1; i <= n; i++) f[i] = i, all[i] = 1;34     for(i = 1; i <= n; i++)35     {36         scanf("%s", s);37         if(s[0] == ‘M‘)38         {39             x = read();40             y = read();41             fx = find(x);42             fy = find(y);43             f[fy] = fx;44             up[fy] += all[fx];45             all[fx] += all[fy];46         }47         else48         {49             x = read();50             fx = find(x);51             printf("%d\n", all[fx] - up[x] - 1);52         }53     }54     return 0;55 }
View Code

 

[luoguP2342] 叠积木（并查集）


联系
我们