逆向并查集 hrbust 1913

#include<iostream> //由于拆除并查集的方法太难或者没有
#include<cstdio> //可以先将所有没有拆的桥连接 再逆向操作 断开变成连接 反向输出
#include<map>
using namespace std;

const int Hash = 10000;
const int N = 10005;
const int M = 20005;

map<int, bool>mp; //mp用来标记该桥是否会被拆，如果会被拆就先不要连接

int f[N];
int rank[N];
int ans[50005]; // ±￡′?′e°?

struct Buit{
int u, v;
}built[M];

struct Query{
char cmd[10];
int a, b;
}query[50005];

int find(int x){
f[x]=f[x]==x?x:find(f[x]);
}
void Union(int x,int y){
int a=find(x),b=find(y);;
if(a==b)return ;
if(rank[a]>rank[b]) f[b]=a;
else if(rank[a]<rank[b]) f[a]=b;
else{
if(a>b) f[a]=b;
else f[b]=a;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int n,m,Q,k,ok=0;
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
scanf("%d",&rank[i]);
scanf("%d",&m);

for(int i=0;i<m;i++){
scanf("%d%d",&built[i].u,&built[i].v);
if(built[i].u>built[i].v)
swap(built[i].u,built[i].v);
}

scanf("%d",&Q);
mp.clear();
for(int i=0;i<Q;i++){
scanf("%s",query[i].cmd);
if(query[i].cmd[0]==‘q‘){
scanf("%d",&query[i].a);
}
else{
scanf("%d%d",&query[i].a,&query[i].b);
if(query[i].a>query[i].b)
swap(query[i].a,query[i].b);
mp[query[i].a*Hash+query[i].b]=true;
}
}
for(int i=0;i<n;i++)
f[i]=i;
for(int i=0;i<m;i++)
if(!mp[built[i].u*Hash+built[i].v])
Union(built[i].u,built[i].v);
k=0;
for(int i=Q-1;i>=0;i--)
{
if(query[i].cmd[0]==‘q‘){
if(rank[find(query[i].a)]>rank[query[i].a])
ans[k++]=find(query[i].a);
else
ans[k++]=-1;
}
else{
Union(query[i].a,query[i].b);
}
}
if(ok)
printf("\n");
ok=1;
for(int i=k-1;i>=0;i--){
printf("%d\n",ans[i]);
}
}
return 0;
}

逆向并查集 hrbust 1913,布布扣,bubuko.com

逆向并查集 hrbust 1913

原文：http://www.cnblogs.com/icodefive/p/3599182.html