题目描述
这是一道被离线的模板题。
你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。
0：加入一条边。保证它不存在。1：删除一条边。保证它存在。2：查询两个点是否联通。
输入格式
输入的第一行是两个数
接下来
输出格式
对于每一个
样例
样例输入 1
200 5
2 123 127
0 123 127
2 123 127
1 127 123
2 123 127样例输出 1
N
Y
N样例输入 2
4 10
0 1 2
0 2 3
0 3 1
2 1 4
0 4 3
2 1 4
1 2 3
2 1 4
1 1 3
2 1 4样例输出 2
N
Y
Y
N数据范围与提示
对于数据点 1，
P.S. 其实 9 是菊花，10 是单链，而没有放随机树的点...
按时间（即操作顺序）建立线段树，可以发现每条边存在的时间是一段区间也就是说会影响到一段时间内的查询
然后用按大小合并的并查集维护一下即可
代码：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<vector>
5 #include<map>
6 #define ls node<<1
7 #define rs node<<1|1
8 #define M 500010
9 using namespace std;
10 int n,m,top,cnt1,cnt2;
11 int fa[M],f[M],size[M];
12 bool vis[M];
13 map<int,int>edge[M];
14 struct point{int u,v;}CG[M],a[M],st[M],Q[M];
15 vector<int>tag[M<<2];
16 void insert(int node,int l,int r,int l1,int r1,int id) {
17 if(l1<=l&&r1>=r) return void(tag[node].push_back(id));
18 int mid=(l+r)/2;
19 if(l1<=mid) insert(ls,l,mid,l1,r1,id);
20 if(r1>mid) insert(rs,mid+1,r,l1,r1,id);
21 }
22 int find(int x) {
23 while(fa[x]!=x) x=fa[x];
24 return x;
25 }
26 void unionn(int x,int y) {
27 x=find(x),y=find(y);
28 if(x==y) return;
29 if(size[x]>size[y]) swap(x,y);
30 st[++top]=(point){x,y};
31 size[fa[x]=y]+=size[x];
32 }
33 void del(int now) {
34 while(top>now) {
35 int x=st[top].u,y=st[top--].v;
36 size[y]-=size[fa[x]=x];
37 }
38 }
39 void Dfs(int node,int l,int r) {
40 int now=top;
41 for(int i=0;i<tag[node].size();i++) {
42 unionn(CG[tag[node][i]].u,CG[tag[node][i]].v);
43 }
44 if(l==r) {
45 if(vis[l])
46 puts(find(Q[l].u)==find(Q[l].v)?"Y":"N");
47 }
48 else{
49 int mid=(l+r)/2;
50 Dfs(ls,l,mid),Dfs(rs,mid+1,r);
51 }del(now);
52 }
53 int main() {
54 scanf("%d%d",&n,&m);
55 for(int i=1;i<=n;i++) fa[i]=i,size[i]=1;
56 for(int i=1;i<=m;i++) {
57 int opt,x,y;
58 scanf("%d%d%d",&opt,&x,&y);
59 if(x>y) swap(x,y);
60 if(opt==0) {
61 if(f[edge[x][y]]) continue;
62 edge[x][y]=++cnt1;
63 a[cnt1]=(point){x,y};
64 f[edge[x][y]]=i;
65 }
66 else if(opt==1) {
67 int id=edge[x][y];
68 CG[++cnt2]=(point){x,y};
69 insert(1,1,m,f[id],i,cnt2);
70 f[id]=0;
71 }
72 else Q[i]=(point){x,y},vis[i]=true;
73 }
74 for(int i=1;i<=cnt1;i++)if(f[i]) {
75 CG[++cnt2]=(point){a[i].u,a[i].v};
76 insert(1,1,m,f[i],m,cnt2);
77 }
78 Dfs(1,1,m);
79 return 0;
80 }