【题意】：
有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