這是一題套用并查集（又稱不相交集）的題
在套用過程中有一個小技巧，可以避免并查集不能刪邊的缺點（當然，在實際應用中實用性不大）。
題意是說有n個星球組成一個連接的網絡，很明顯把星球看成點而有通訊連線看成有邊相連，接下來有m個操作，有查詢操作，添加邊的操作和銷毀邊的操作，同時每個星球有一個權值，即每個點有一個權值，對一個點的查詢操作返回的是與它間接或直接相連的星球中權值最大者的序號。
首先，查詢的操作很明顯帶有自反對稱和傳遞性，易想到用并查集來解決，但是并查集只有添加邊和查詢兩種操作（如對并查集不明可baidu之，很多網頁都有講，是比較基礎的數據結構，實現過程也很簡單，又稱不相交集），故需要一些技巧，就是讀入并記錄所有的操作，從最后一條操作開始處理，一開始的圖是給定的圖刪去后來需要銷毀的邊后的圖，記錄答案，當讀到銷毀操作時再把需銷毀的邊加上去，這樣就可以回避銷毀操作（倒著來事實上把銷毀操作變成了加邊的操作）。
在實現時，可用vector來存答案和操作，節(jié)省代碼量。
附上我的代碼
1
#include <cstdio>
2#include <vector>
3#include <utility>
4#include <algorithm>
5
6using namespace std;
7
8template<int MAXN>
9
struct DisjointSet 
{
10
int p[MAXN];
11 int s[MAXN];
12
13
void init(int n) {
14 for (int i = 0; i < n; i++) {
15 p[i] = i;
16
}
17 }
18
19 int root(int x) {
20 return p[x] == x ? x : (p[x] = root(p[x]));
21 }
22
23 bool is_friend(int i, int j) {
24 return root(i) == root(j);
25 }
26
27 void set_friend(int i, int j) {
28 i = root(i);
29 j = root(j);
30 if (i != j) {
31 if (s[i] > s[j] || (s[i] == s[j] && i < j)) {
32 p[j] = i;
33 } else {
34 p[i] = j;
35 }
36 }
37 }
38
};
39
40DisjointSet<10086> dset;
41
42int main() {
43 bool blank = false;
44 char buf[1024];
45 int n, m, q, a, b;
46
47 while (scanf("%d", &n) != EOF) {
48 if (blank) {
49 puts("");
50 } else {
51 blank = true;
52 }
53 dset.init(n);
54 for (int i = 0; i < n; ++i) {
55 scanf("%d", &dset.s[i]);
56 }
57 vector<pair<int, int> > v, vv, w;
58 scanf("%d", &m);
59 for (int i = 0; i < m; ++i) {
60 scanf("%d%d", &a, &b);
61 if (a > b) {
62 swap(a, b);
63 }
64 v.push_back(make_pair(a, b));
65 }
66 scanf("%d ", &q);
67 for (int i = 0; i < q; ++i) {
68 fgets(buf, sizeof(buf), stdin);
69 b = -1;
70 sscanf(buf, "%*s%d%d", &a, &b);
71 if (a > b) {
72 swap(a, b);
73 }
74 w.push_back(make_pair(a, b));
75 if (a != -1) {
76 vv.push_back(make_pair(a, b));
77 }
78 }
79
80 sort(v.begin(), v.end());
81 sort(vv.begin(), vv.end());
82 v.erase(set_difference(v.begin(), v.end(), vv.begin(), vv.end(), v.begin()), v.end());
83 for (vector<pair<int, int> >::const_iterator it = v.begin(); it != v.end(); ++it) {
84 dset.set_friend(it->first, it->second);
85 }
86 vector<int> ans;
87 while (!w.empty()) {
88 if (w.back().first == -1) {
89 b = w.back().second;
90 a = dset.root(b);
91 ans.push_back(dset.s[a] > dset.s[b] ? a : -1);
92 } else {
93 dset.set_friend(w.back().first, w.back().second);
94 }
95 w.pop_back();
96 }
97 int i;
98 for (i=ans.size()-1; i>=0; i--)
99 printf("%d\n",ans[i]);
100 }
101
102
103 return 0;
104}
對并查集是用class來實現。。