zoj3261 Connections in Galaxy War

 

#include<stdio.h>
#include<vector>
using 
namespace std;

int 
pow[10005];
int 
pre[10005];
vector<int> map[10005];

struct Node
{
    char 
s;
    int a,b,ans;
};
Node 
node[50005];


int find(int x)
{
    if(pre[x]==x) return 
x;
    pre[x]=find(pre[x]);
    return pre[x];
}

void 
merge(int x1,int x2)
{
    int 
root1=find(x1);
    int 
root2=find(x2);
    if(root1==root2) return ;
    if(pow[root1]>pow[root2]) pre[root2]=root1;
    else 
if(pow[root1]<pow[root2]) pre[root1]=root2;
    else
    {                                
        if(root1>root2) 
pre[root1]=root2;
        else pre[root2]=root1;
    }
}

int 
main()
{
    int 
n;
    bool first=true;
    while(scanf("%d",&n)!=EOF)
    {
        if(first) first=false;else printf("\n");
        for(int i=0;i<n;i++)
        {
            scanf("%d",&pow[i]);
            pre[i]=i;
            map[i].clear();
        }

        int m;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {    
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>b){int temp=a;a=b;b=temp;} //规定方向以避免重复
            map[a].push_back(b);
        }

        int q;
        scanf("%d",&q);
        char str[10];
        for(int i=0;i<q;i++)        
        {
            scanf("%s",str);
            if(str[0]=='q')
            {
                int a;
                scanf("%d",&a);
                node[i].a=a;
                node[i].b=0;
                node[i].s='q';
            }
            else
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if(a>b){int temp=a;a=b;b=temp;}
                node[i].a=a;
                node[i].b=b;
                node[i].s='d';

                for(vector<int>::iterator 
it=map[a].begin();it!=map[a].end();it++)
                {
                    if(*it>=0&&*it==b)
                    {
                        *it=-1;break;
                    }
                }
            }
        }

        for(int i=0;i<n;i++)
        {
            for(vector<int>::iterator 
it=map[i].begin();it!=map[i].end();it++)
            {
                if(*it>=0) merge(i,*it);
            }
        }

        for(int i=q-1;i>=0;i--)
        {
            if(node[i].s=='q')
            {
                int root=find(node[i].a);
                node[i].ans=pow[root]>pow[node[i].a]?root:-1;
            }
            else
            {
                merge(node[i].a,node[i].b); //只要两点位于同一集合就说明其是连通的
            }
        }

        for(int i=0;i<q;i++)
            if(node[i].s=='q') printf("%d\n",node[i].ans);
    }
    return 0;
}

总结：

很巧妙的一道并查集~~先把所有的命令存起来，根据最终状态的构图，将每一个连通分量转化成
一个集合，树根是能量最大的星球，若存在多个能量最大的星球，则取编号最小的星球，之后逆
向读取每个命令，若为查询则比对树根和该星球的能量大小，若是消边则并入集合，因为是逆向
处理，该命令之前的构图中存在这两个星球的连接，因而是相反的操作。