SSL 1255_银河英雄传说_并查集

发布于 2019-04-28  830 次阅读


题目大意

一开始用一字整形,然后为了战斗,就要调整队形,他可以把i行舰队的所有飞船都搞到j行去。
同时他也想知道两个飞船之间有多少飞船。
如果不在同一列就输出-1.

思路

在并查集时加上一个数组记录当前数在这一列的位置和最后面的数,然后搞一下就可以了

#include 
#include 
#define MAX 300000
int f[MAX],d[MAX],last[MAX];
int ll=0;
int find(int x)
{
    if (x!=f[x]) ll=find(f[x]);
                 else ll=x;
    if (f[x]!=f[f[x]]) d[x]=d[x]+d[f[x]];
    f[x]=ll;
    return ll;
}
int main()
{
    char st[10];
    int n;
    scanf("%d",&n);
    for (int i=1;i<=MAX-1;i++)
    {
        f[i]=i;
        last[i]=1;
    }

    for (int i=1;i<=n;i++)
    {
        int x,y;
        st[0]='p';
        while (st[0]!='M'&&st[0]!='C')
            st[0]=getchar();
        getchar();
        scanf("%d%d",&x,&y);
        int dx=find(x),dy=find(y);
        if (st[0]=='M')
        {
            f[dx]=dy;
            d[dx]=last[dy];
            last[dy]=last[dx]+last[dy];
        }
        if (st[0]=='C')
        {
            if (dx!=dy) printf("-1\n");
            else 
            {
                int ans=d[x]-d[y];
                if (ans<0) ans=-ans;
                ans--;
                printf("%d\n",ans);
            }
        }
    }
}
]]>