這是一題套用并查集（又稱(chēng)不相交集）的題
在套用過(guò)程中有一個(gè)小技巧，可以避免并查集不能刪邊的缺點(diǎn)（當(dāng)然，在實(shí)際應(yīng)用中實(shí)用性不大）。
題意是說(shuō)有n個(gè)星球組成一個(gè)連接的網(wǎng)絡(luò)，很明顯把星球看成點(diǎn)而有通訊連線看成有邊相連，接下來(lái)有m個(gè)操作，有查詢(xún)操作，添加邊的操作和銷(xiāo)毀邊的操作，同時(shí)每個(gè)星球有一個(gè)權(quán)值，即每個(gè)點(diǎn)有一個(gè)權(quán)值，對(duì)一個(gè)點(diǎn)的查詢(xún)操作返回的是與它間接或直接相連的星球中權(quán)值最大者的序號(hào)。
首先，查詢(xún)的操作很明顯帶有自反對(duì)稱(chēng)和傳遞性，易想到用并查集來(lái)解決，但是并查集只有添加邊和查詢(xún)兩種操作（如對(duì)并查集不明可baidu之，很多網(wǎng)頁(yè)都有講，是比較基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)過(guò)程也很簡(jiǎn)單，又稱(chēng)不相交集），故需要一些技巧，就是讀入并記錄所有的操作，從最后一條操作開(kāi)始處理，一開(kāi)始的圖是給定的圖刪去后來(lái)需要銷(xiāo)毀的邊后的圖，記錄答案，當(dāng)讀到銷(xiāo)毀操作時(shí)再把需銷(xiāo)毀的邊加上去，這樣就可以回避銷(xiāo)毀操作（倒著來(lái)事實(shí)上把銷(xiāo)毀操作變成了加邊的操作）。
在實(shí)現(xiàn)時(shí)，可用vector來(lái)存答案和操作，節(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}
對(duì)并查集是用class來(lái)實(shí)現(xiàn)。。