Problem

给定两张有$n(n \le 10^5)$个点的图，原图中至多$k(k \le 10^5)$条边

给定$m(m \le 10^5)$个操作，操作分三类：

1. 在第一张图中增加一条边
2. 在第二张图中增加一条边
3. 查询a点在第二张图中直接相连的点中，能够在第一张图中直接或者间接到达的数量

Solution

我们用并查集维护第一张图，在对应的集合上记录在第二张图中出现但在第一张图中未连通的点对

当发生操作一时我们对集合进行启发式合并，将未连通点对数量少的集合并入未连通点对数量多的点对

发生点对连通时，我们修改对应两个点的答案，并将点对记录删去

总复杂度$O(Mlog(M))$，其中$M=2*(m+k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 100000 + 10;
set<pair<int, int>> st[N];
int n, m, k, q, f[N], ans[N];
int sf(int x) { return f[x] == x ? x : f[x] = sf(f[x]); }
void merge(int x, int y) {
    if (x == y) return;
    if (st[x].size() > st[y].size()) swap(x, y);
    for (auto u : st[x]) {
        if (st[y].count(u)) {
            ans[u.fi]++;
            ans[u.se]++;
            st[y].erase(u);
        } else {
            st[y].insert(u);
        }
    }
    f[x] = y;
}
char op[10];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        st[a].insert({a, b});
        st[b].insert({a, b});
    }
    for (int i = 1; i <= k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        merge(sf(a), sf(b));
    }
    scanf("%d", &q);
    while (q--) {
        scanf("%s", op);
        if (op[0] == '?') {
            int x;
            scanf("%d", &x);
            printf("%d\n", ans[x]);
        }
        if (op[0] == 'T') {
            int x, y;
            scanf("%d%d", &x, &y);
            merge(sf(x), sf(y));
        }
        if (op[0] == 'F') {
            int x, y;
            scanf("%d%d", &x, &y);
            if (sf(x) == sf(y)) {
                ans[x]++;
                ans[y]++;
            } else {
                st[sf(x)].insert({x, y});
                st[sf(y)].insert({x, y});
            }
        }
    }
    return 0;
}