kuangbin专题五 并查集 ZOJ3261 Connections in Galaxy War

题意：
银河系各大星球之间有不同的能量值， 并且他们之间互相有通道连接起来，可以用来传递信息，这样一旦A星球被另一维度的怪物攻击，便可通过通道找到能量值比A星球大的星球来帮忙。但是有一些通道被怪物破坏了。
现在先给出原来的所有通道， 然后进行询问，询问有两种方式：
destroy a b： 连接a，b的通道被怪兽破坏了
query a: 询问a能否通过通道找到救兵。
题解：
考察你对并查集的理解程度，并查集是把边合并起来，让他们尽量集中到一个祖宗那里去，而这道题要求的是删边，那么我们可以逆过来想这道题，把Q中的询问和删变操作保存下来保存下来，我们在进行Q操作之前我们先并查集M中的边，对于Q中要求删除的边先不用管。再从Q的操作后面开始写起来，然后把删除的边用并查集合起来，这样就可以得到答案了，然后你会发现你超时了，还得优化一下，可以用map容器进行优化。这题还有一个坑点，也不算坑点，因为是我没注意的。。这题的点是从0开始的，不是从1开始的。。。

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN=1e4+7;
const int MAXM=5e4+7;
struct node1
{
    int power,f;
}a[MAXN];
struct node2
{
    int u,v;
}b[MAXM];
struct node3
{
    char s[10];
    int u,v;
}q[MAXM];
map<int,bool>mark[MAXN];
int n,m,k;
int ans[MAXM];
void init()
{
    memset(ans,0,sizeof(ans));
    for(int i=0;i<n;i++)
    mark[i].clear();
    for(int i=0;i<n;i++)
    a[i].f=i,a[i].power=0;
}
int find(int p)
{
    while(p!=a[p].f)
    {
        int temp=a[p].f;
        a[p].f=find(temp);
        a[p].f=a[temp].f;
        p=a[p].f;
    }
    return p;
}
void Union(int p,int q)
{
    int P=find(p);
    int Q=find(q);
    if(P==Q)
    return ;
    else
    {
        if(a[P].power==a[Q].power&&P>Q)
        {
            int t=P;
            P=Q;
            Q=t;
        }
        else if(a[P].power<a[Q].power)
        {
            int t=P;
            P=Q;
            Q=t;
        }
        a[Q].f=P;
    }
}
int main()
{
    bool flag=false;
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0;i<n;i++)
        scanf("%d",&a[i].power);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        scanf("%d%d",&b[i].u,&b[i].v);
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
            scanf("%s",q[i].s);
            if(q[i].s[0]=='q')
            scanf("%d",&q[i].u);
            else{
                scanf("%d%d",&q[i].u,&q[i].v);
                mark[q[i].u][q[i].v]=mark[q[i].v][q[i].u]=true;             
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(mark[b[i].u][b[i].v])
            continue;
            Union(b[i].u,b[i].v);
        }
        for(int i=k;i>=1;i--)
        {
            if(q[i].s[0]=='d')
            Union(q[i].u,q[i].v);
            else
            {
                int P=find(q[i].u);
//              if(P==q[i].u)//这种写法不知道为啥错误 
//              ans[i]=-1;
//              else
//              ans[i]=P;
                ans[i]=a[P].power>a[q[i].u].power?P:-1;     
            }
        }
        if(flag)
        printf("\n");
        else
        flag=true;
        for(int i=1;i<=k;i++)
        if(q[i].s[0]=='q')
        printf("%d\n",ans[i]);
    }
}