首页 > 代码库 > 2014 Super Training #8 A Gears --并查集

2014 Super Training #8 A Gears --并查集

2024-07-11 21:34:27   222人阅读

题意：

有N个齿轮，三种操作
1.操作L x y：把齿轮x,y链接，若x,y已经属于某个齿轮组中，则这两组也会合并。
2.操作Q x y：询问x,y旋转方向是否相同（等价于齿轮x,y的相对距离的奇偶性）。
3.操作D x ：拆下齿轮x，并且x所在的齿轮组不会断开
4.操作S x ： 查询齿轮x所在的齿轮组有多少齿轮。
并查集，维护父节点的同时，dis记录一下每个节点到根节点的距离，并且用num记录一下以x为根节点的集合有多少个元素。

由于涉及到删除操作，删除的是根节点的话会导致信息丢失，所以在删除的时候直接新建一个节点，所以再加一个变量，表示节点x所对应的实际节点编号mp[x]。

这样fa[x]表示x的父节点，mp[x]表示x实际的编号（从N+1开始记）

（copied）

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;#define N 600007#define M 33int fa[N],n,m,dis[N];int num[N],mp[N];int findset(int x){    if(x != fa[x])    {        int tmp = findset(fa[x]);        dis[x] += dis[fa[x]];  //累加距离        fa[x] = tmp;    }    return fa[x];}void init(){    for(int i=0;i<=n+m;i++)    {        fa[i] = i;        num[i] = 1;        dis[i] = 0;        mp[i] = i;    }}int main(){    int i,u,v,k;    char ss[5];    while(scanf("%d%d",&n,&m)!=EOF)    {        init();        int now = n+1;        while(m--)        {            scanf("%s",ss);            if(ss[0] == ‘L‘)            {                scanf("%d%d",&u,&v);                u = mp[u];  //实际的位置                v = mp[v];                int fx = findset(u);                int fy = findset(v);                if(fx != fy)                {                    fa[fx] = fy;                    //dis[fx] = dis[fy]+1; //1                    //dis[u] = dis[v]+1;   //2  **1,2顺序不能反，或者直接用下面**                    dis[fx] = dis[u]+dis[v]+1;   //与根距离之和的奇偶性再反一下，得出相对距离的奇偶性                    num[fy] += num[fx];                }            }            else if(ss[0] == ‘Q‘)            {                scanf("%d%d",&u,&v);                u = mp[u];    //实际的位置                v = mp[v];                int fx = findset(u);                int fy = findset(v);                if(fx != fy)                    puts("Unknown");                else                {                    if(abs(dis[u]-dis[v]) & 1)                        puts("Different");                    else                        puts("Same");                }            }            else if(ss[0] == ‘S‘)            {                scanf("%d",&u);                int tu = mp[u];                printf("%d\n",num[findset(tu)]);            }            else            {                scanf("%d",&v);                int tv = mp[v];                num[findset(tv)]--;                mp[v] = now++;            }        }    }    return 0;}
View Code

 

 


联系
我们