Connections in Galaxy War——逆向并查集

题目链接

题意：

首先给定一个n 然后给你 n个数表示每个恒星的能量大小 p【i】然后给定一个m 然后输入m 条恒星之间的连接关系

再给定一个q q行如果 query x 表示查询与 x 号恒星连接并且能量最多的恒星编号如果 destroy x y 表示破环 x恒星与y恒星之间的连接

题解：

传统的做法是先把输入的点加入并查集建立关系，然后开始判断询问，遇到destroy就将那两个点之间的关系断开，但是很明显，这样很难做到将其连接关系断开

正难则反

我们先把未被destroy的恒星连接起来，这样我们就可以从最后一个询问开始判断并记录下结果，当遇到destroy时再把这两个点建立关系，这样destroy前面的询问就可以正确地判断了

如何把未被destroy的恒星连接起来？

先把所有星球的连接关系存起来，然后把destroy的的恒星标记起来，没被标记的就是未被destroy的，然后 join() 一下即可

注意恒星的编号是从 0 开始的还要保证输入的编号 u，v 要保证 u<v 即（有序即可）不然可能会出现，加边的时候是1,2但是删边的时候是2,1的情况

代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int Hash=1000;
int n,m;
int p[maxn],f[maxn],ans[maxn];
int pos[maxn],maxx[maxn];
struct node
{
    int x,y;
}a[maxn];
struct edge
{
    int op,x,y;
}e[maxn];
map<int,int>vis;
char s[maxn];
int Find(int x)
{
    return f[x]==x?x:f[x]=Find(f[x]);
}
void join(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
    {
        f[fx]=fy;
        if(maxx[fx]>maxx[fy])
        {
            maxx[fy]=maxx[fx];
            pos[fy]=pos[fx];
        }
        else if(maxx[fx]==maxx[fy] && pos[fx]<pos[fy])
        {
            pos[fy]=pos[fx];
        }
    }
}
int main()
{
    int flag=0;
    while(~scanf("%d",&n))
    {

        if(flag)printf("\n");
        else flag=1;

        for(int i=0;i<n;i++)
        {
            scanf("%d",&p[i]);
            maxx[i]=p[i];
            pos[i]=i;
            f[i]=i;
        }

        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
        }
        int q;
        scanf("%d",&q);
        vis.clear();
        for(int i=0;i<q;i++)
        {
            scanf("%s",s);
            if(s[0]=='q')
            {
                e[i].op=0;
                scanf("%d",&e[i].x);
            }
            else
            {
                e[i].op=1;
                scanf("%d%d",&e[i].x,&e[i].y);
                if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
                vis[e[i].x*Hash+e[i].y]=1;
            }
        }
        for(int i=0;i<m;i++)
        {
            if(!vis[a[i].x*Hash+a[i].y])join(a[i].x,a[i].y);
        }
        int cnt=0;

        for(int i=q-1;i>=0;i--)
        {
            if(e[i].op==0)
            {
                int x=e[i].x;
                int fx=Find(x);
                if(maxx[fx]>p[x])ans[cnt++]=pos[fx];
                else ans[cnt++]=-1;
            }
            else
            {
                join(e[i].x,e[i].y);
            }
        }
        for(int i=cnt-1;i>=0;i--)printf("%d\n",ans[i]);

    }
    return 0;
}

View Code

Connections in Galaxy War——逆向并查集

相关推荐