【題意】：
有n個島，初始沒有橋，每次可以在i和j間建一座橋，拆一座橋，或查詢i和j是否聯通，i和j之間最多只會建一次橋。
點數n=500，操作數m=50000。
【題解】：
由于點數只有500，其實這題不需要任何高級的數據結構就有一個O(n*m)的算法。注意到點數很少，而要求i和j是否聯通，我們只要保留這幅圖的生成森林就足夠了，即控制邊的個數為O(n)。對于查詢操作，直接dfs一次即可。對于加邊操作，如果i和j不聯通，那么直接加上這條邊就好了。否則，加上這條邊后一定形成一個圈，如果我們把這個圈中最早被刪去的邊提前刪掉，是不會影響后面操作的結果的，所以我們刪掉這條邊，以保證圖中始終沒有圈。對于刪邊操作，如果這個邊已經被提前刪掉了，那么什么也不做，否則簡單刪掉就好了。要知道哪條邊先被刪掉，可以先讀入所有操作，預處理之。對于每次操作，復雜度均為O(n)，總的復雜度O(n*m)。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 550
26 #define maxm 50050
27 int n, m;
28 int a[maxm], b[maxm];
29 int d[maxn][maxn];
30 char c[maxm];
31 vector<int> vec[maxn];
32 int x, y, z;
33
34 bool dfs(int s, int t, int fa) {
35 if(s == t) return true;
36 for(vector<int>::const_iterator it = vec[s].begin(); it != vec[s].end(); it++) {
37 if(*it != fa && dfs(*it, t, s)) {
38 if(z > d[s][*it]) {
39 x = s;
40 y = *it;
41 z = d[x][y];
42 }
43 return true;
44 }
45 }
46 return false;
47 }
48
49 int main() {
50 int Case = 1;
51 while(cin >> n >> m) {
52 for(int i = 0; i <= n; i++) {
53 vec[i].clear();
54 fill(d[i], d[i] + n, maxm);
55 }
56 for(int i = 0; i < m; i++) {
57 scanf(" %c%d%d", &c[i], &a[i], &b[i]);
58 if(c[i] == 'D') d[a[i]][b[i]] = d[b[i]][a[i]] = i;
59 }
60 if(Case > 1) puts("");
61 printf("Case %d:\n", Case++);
62 for(int i = 0; i < m; i++) {
63 if(c[i] == 'I') {
64 z = maxm;
65 if(dfs(a[i], b[i], -1)) {
66 if(z < d[a[i]][b[i]]) {
67 vec[x].erase(remove(vec[x].begin(), vec[x].end(), y), vec[x].end());
68 vec[y].erase(remove(vec[y].begin(), vec[y].end(), x), vec[y].end());
69 vec[a[i]].pb(b[i]);
70 vec[b[i]].pb(a[i]);
71 }
72 } else {
73 vec[a[i]].pb(b[i]);
74 vec[b[i]].pb(a[i]);
75 }
76 } else if(c[i] == 'D') {
77 vec[a[i]].erase(remove(vec[a[i]].begin(), vec[a[i]].end(), b[i]), vec[a[i]].end());
78 vec[b[i]].erase(remove(vec[b[i]].begin(), vec[b[i]].end(), a[i]), vec[b[i]].end());
79 } else {
80 puts(dfs(a[i], b[i], -1) ? "YES" : "NO");
81 }
82 }
83 }
84 return 0;
85 }
86