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;
}