ZOJ 3261 Connections in Galaxy War （并查集+离线处理）

Description：

In order to strengthen the defense ability, many stars in galaxy allied together and built many bidirectional tunnels to exchange messages. However, when the Galaxy War began, some tunnels were destroyed by the monsters from another dimension. Then many problems were raised when some of the stars wanted to seek help from the others.

In the galaxy, the stars are numbered from 0 to N-1 and their power was marked by a non-negative integer pi. When the star A wanted to seek help, it would send the message to the star with the largest power which was connected with star A directly or indirectly. In addition, this star should be more powerful than the star A. If there were more than one star which had the same largest power, then the one with the smallest serial number was chosen. And therefore, sometimes star A couldn't find such star for help.

Given the information of the war and the queries about some particular stars, for each query, please find out whether this star could seek another star for help and which star should be chosen.

 

Input

 

There are no more than 20 cases. Process to the end of file.

For each cases, the first line contains an integer N (1 <= N <= 10000), which is the number of stars. The second line contains N integers p0, p1, ... , pn-1 (0 <= pi <= 1000000000), representing the power of the i-th star. Then the third line is a single integer M (0 <= M <= 20000), that is the number of tunnels built before the war. Then M lines follows. Each line has two integers a, b (0 <= a, b <= N - 1, a != b), which means star a and star b has a connection tunnel. It's guaranteed that each connection will only be described once.

In the (M + 2)-th line is an integer Q (0 <= Q <= 50000) which is the number of the information and queries. In the following Q lines, each line will be written in one of next two formats.

"destroy a b" - the connection between star a and star b was destroyed by the monsters. It's guaranteed that the connection between star a and star b was available before the monsters' attack.

"query a" - star a wanted to know which star it should turn to for help

There is a blank line between consecutive cases.

Output

For each query in the input, if there is no star that star a can turn to for help, then output "-1"; otherwise, output the serial number of the chosen star.

Print a blank line between consecutive cases.

 

Sample Input

 

2 10 20 1 0 1 5 query 0 query 1 destroy 0 1 query 0 query 1

 

Sample Output

 

1 -1 -1 -1

     有n个点和m条边，每个点带有一个权值p[i]。现在给出Q条命令，要你输出对应的答案。命令格式如下：

        query u ：该命令需要输出当前与u点相连的点编号x，x要满足p[x]是所有与u相连的点中最大的 且 p[x]>p[u]。如果有多个满足条件的x存在，那么就输出编号最小的那个x点的编号。

        destroy u v：该命令将删除u与v的边。(保证在执行该命令前u与v之间有一条边)

 每个点看成并查集中的一个点，那么query u的时候就是查找u所属的连通分量中p[]值最大的点编号。所以我们可以始终让一个连通分量的根就是那个p[]值最大的点 且 在合并连通分量的时候依然维持这一性质。

        由于并查集只能增加边，而题目的命令却只有删除边，所以自然想到将所有命令先预读入内存，然后从最后一条命令往前，一条一条添加边处理。

        具体处理过程如下：

        首先我们读入M条边，但是此时先不连接任何边。接着我们读入每条命令，并且将会被删除的边标记出来。然后我们将那些没有被删除的边都用并查集连接起来。

        然后我们逆序处理每条命令(从最后一条命令开始)，如果是query命令就是返回该分量的根编号(还需要判断根的p值是否>u的p值)。如果是destory u v 命令，其实就是添加u v边的命令。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
const int INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

const int maxn=10000+5;

int p[maxn];//power值

//并查集
int fa[maxn];
int findset(int x)
{
    return fa[x]==-1? x:fa[x]=findset(fa[x]);
}
int bind(int u,int v)
{
    int fu=findset(u);
    int fv=findset(v);
    if(fu != fv)
    {
        if(p[fu]>p[fv] || (p[fu]==p[fv] && fu<fv) )//fu是根
        {
            fa[fv]=fu;
        }
        else//fv是根
        {
            fa[fu]=fv;
        }
        return 1;
    }
    return 0;
}

//边
struct Edge
{
    int u,v;
    Edge() {}
    Edge(int u,int v):u(u),v(v) {}

    bool operator<(const Edge &rhs)const
    {
        return u<rhs.u || (u==rhs.u && v<rhs.v);
    }
} edges[20000+5];
bool vis[20000+5];

//命令
struct command
{
    int type;
    int v;
} coms[50000+5];

int main()
{
    int n,m,Q;
    bool first=true;
    while(scanf("%d",&n)==1)
    {
        if(!first)
            printf("\n");
        first=false;
        for(int i=0; i<n; i++)
            scanf("%d",&p[i]);
        scanf("%d",&m);
        map<Edge,int> mp;//边与边的编号的映射
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(u>v)
                swap(u,v);
            edges[i]=Edge(u,v);//可优化
            mp[edges[i]]=i;
        }
        memset(vis,0,sizeof(vis));//vis[i]==true表第i条边已被删除
        scanf("%d",&Q);
        for(int i=0; i<Q; i++)
        {
            char str[100];
            int u,v;

            scanf("%s",str);
            if(str[0]=='q')
            {
                scanf("%d",&u);

                coms[i].type=0;
                coms[i].v=u;
            }
            else if(str[0]=='d')
            {
                scanf("%d%d",&u,&v);
                if(u>v) swap(u,v);
                int id=mp[Edge(u,v)];//获取对应边的编号

                vis[id]=1;//删除此边
                coms[i].type = 1;
                coms[i].v=id;
            }
        }
        //连通所有未被删除的边
        memset(fa,-1,sizeof(fa));
        for(int i=0; i<m; i++)if(vis[i]==false)
            {
                bind(edges[i].u,edges[i].v);
            }
        //逆序处理所有命令并将query结果保存在vc中
        vector<int> vc;
        for(int i=Q-1; i>=0; i--)
        {
            if(coms[i].type == 0)//query命令
            {
                int root = findset(coms[i].v);
                if(p[root]>p[coms[i].v])
                    vc.push_back(root);
                else
                    vc.push_back(-1);
            }
            else//destroy命令
            {
                int u=edges[coms[i].v].u, v=edges[coms[i].v].v;
                bind(u,v);
            }
        }
        for(int i=vc.size()-1; i>=0; i--)
            printf("%d\n",vc[i]);
    }
    return 0;
}