题意
n 个星球，m 条道路， q 个命令。战争爆发了， 命令被分为两种： 1.战争破坏了星球 a 和 b 之间的道路。 2. a 星球发出求救信号，输出求救对象。 选择求救对象的规则如下： 1.选择 a 星球能够到达的战斗力（题中给出每个星球的战斗力）最高的星球。 2.如果最高战斗力的星球有两个，取编号较小的那个。 3.求救对象的战斗力必须大于 a 星球。 若符合规则的求救对象存在，输出该编号。否则，输出 -1 。
思路
显然是连通性问题，考虑用并查集来做。 但是并查集能高效地支持 添加边 地操作，而本题主要是删除边地操作。 为此，要把删除边转换成添加边。 具体做法是，把所有的命令保存下来，从后往前倒着执行。即先把被破坏掉的道路全部破坏掉，然后倒着读命令。读到命令 2 ，并查集查找即可。读到命令 1，则向并查集中加入这条边。 如此就把删除边转变成了添加边。
这样做需要记录命令和边。记录边时，由于点数较大，不能采用邻接矩阵。AC代码中是用一个 edge 数组保存边。但这样做的问题是 删除全部被破坏的边时，对应边不容易查找。这里的解决方法是，读入边的时候，用 map 保存边对应的编号。
最后一点，这题的格式比较严格。
题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3261
AC代码
using namespace std;
typedef pair<
int,
int> P;
const
int maxn =
1e4 +
10;
const
int maxm =
2e4 +
10;
const
int maxq =
5e4 +
10;
int n,
m,
q;
char
s[
27];
int x,
y;
int power[maxn];
P edge[maxm];
bool des[maxm];
map<P,
int> M;
int qx[maxq], qy[maxq];
int root[maxn];
int ans[maxq], it;
int Uf(
int x)
{
if(root[
x] == -
1)
return x;
return root[
x] = Uf(root[
x]);
}
void Union(
int x,
int y)
{
x = Uf(
x),
y = Uf(
y);
if(
x ==
y)
return;
if(power[
x] < power[
y]) root[
x] =
y;
else if(power[
x] == power[
y] &&
y <
x) root[
x] =
y;
else root[
y] =
x;
}
int main()
{
//freopen(
"in.txt",
"r", stdin);
bool first = true;
while(scanf(
"%d", &n) != EOF)
{
if(first) first = false;
else printf(
"\n");
memset(des, false, sizeof des);
M.clear();
for(
int i=
0; i< n; i++)
scanf(
"%d", power + i);
scanf(
"%d", &
m);
for(
int i=
0; i<
m; i++)
{
scanf(
"%d %d", &
x, &
y);
if(
x >
y) swap(
x,
y);
edge[i] = P(
x,
y);
M[edge[i]] = i;
}
scanf(
"%d", &
q);
for(
int i=
0; i<
q; i++)
{
scanf(
" %s",
s);
if(
s[
0] ==
'q')
{
scanf(
"%d", &
qx[i]);
qy[i] = -
1;
}
else{
scanf(
"%d %d", &
x, &
y);
if(
x >
y) swap(
x,
y);
qx[i] =
x, qy[i] =
y;
int d = M[P(
x,
y)];
des[d] = true;
}
}
memset(root, -
1, sizeof root);
for(
int i=
0; i<
m; i++)
if(!des[i]) Union(edge[i].first, edge[i].second);
it =
0;
for(
int i=
q-
1; i>=
0; i--)
{
if(qy[i] == -
1)
{
int d = Uf(
qx[i]);
ans[it ++] = power[d] > power[
qx[i]] ? d : -
1;
}
else Union(
qx[i], qy[i]);
}
for(
int i= it -
1; i>=
0; -- i)
printf(
"%d\n", ans[i]);
}
return 0;
}
