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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#define maxn 5010
#define maxm 500010
using namespace std;
int n, m;
struct Edge {
int fr, to;
friend bool operator < (const Edge &u, const Edge &v) {
if (u.fr == v.fr) return u.to < v.to;
return u.fr < v.fr;
}
} ask[maxm]; map<Edge, int> mp;
int fa[maxn], dep[maxn], st[maxn], top;
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, dep[i] = 1; }
int find(int x) {
while (x != fa[x]) x = fa[x];
return x;
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
if (dep[fx] > dep[fy]) swap(fx, fy);
fa[fx] = fy; st[++top] = fx;
if (dep[fx] == dep[fy]) ++dep[fy], st[top] *= -1;
}
void undo(int _top) {
while (top > _top) {
int x = st[top--];
if (x < 0) x = -x, --dep[fa[x]];
fa[x] = x;
}
}
#define lc i << 1
#define rc i << 1 | 1
vector<Edge> T[maxm * 4];
void update(int i, int l, int r, int L, int R, const Edge &v) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return T[i].push_back(v);
int m = l + r >> 1;
update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}
void query(int i, int l, int r) {
if (d[r] - d[l - 1] == 0) return;
int m = l + r >> 1, _top = top;
for (auto v : T[i]) merge(v.fr, v.to);
if (l == r) {
int u = ask[l].fr, v = ask[l].to;
if (u) cout << (find(u) == find(v) ? "Y" : "N") << "\n";
undo(_top); return ;
}
query(lc, l, m); query(rc, m + 1, r);
undo(_top);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; init_fa(n);
for (int i = 1; i <= m; ++i) {
int opt, x, y; cin >> opt >> x >> y;
if (x > y) swap(x, y);
if (opt == 2) ask[i] = { x, y };
else if (opt == 0) mp[{ x, y }] = i;
else update(1, 1, m, mp[{ x, y }], i - 1, { x, y }), mp.erase({ x, y });
}
for (auto u : mp) update(1, 1, m, u.second, m, u.first);
query(1, 1, m);
return 0;
}
|