P1196 NOI2002银河英雄传说


通过带权并查集维护距离

#include<bits/stdc++.h>
using namespace std;
const int maxn=30010;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') t=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int t,d[maxn],fa[maxn],size[maxn];
int findx(int x)
{
    if(x==fa[x]) return x;
    int root=findx(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=root;
}
int main()
{
    t=read();
    for(int i=1;i<=30000;i++) 
    {
        fa[i]=i;
        size[i]=1;
    }
    for(int i=1;i<=t;i++)
    {
        int x,y;
        char s[5];
        scanf("%s",s);
        x=read(),y=read();
        int fi=findx(x),fj=findx(y);
        if(s[0]=='M')
        {
            fa[fi]=fj;
            d[fi]=size[fj];
            size[fj]+=size[fi];
        }
        else 
        {
            if(fi!=fj) printf("-1\n");
            else printf("%d\n",abs(d[x]-d[y])-1);
        }
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ1733Parity game POJ1733Parity game
这道题给出区间奇偶性判断对错,可以维护l-1与r这样一个前缀和,假如两前缀和奇偶相同,那区间就为偶,假如奇偶不同,那区间就为奇,由于区间范围过大,可以考虑离散化,之后通过扩展域解决 #include<cstdio> #include
2019-07-05
下一篇 
P1955 NOI2015程序自动分析 P1955 NOI2015程序自动分析
这道题其实就是把相等的两个点用并查集维护,首先通过排序把相等的放在前面建立集合,然后再通过不等判断是否处在同一集合,由于ij规模过大,要先离散化 #include<bits/stdc++.h> using namespace std
2019-07-05
  目录