# 神奇化合物

## 解法一：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#define MX 800008
#define MQ 10001
using namespace std;

struct graph
{
int n;
int fst[MX],nxt[MX],u[MX],v[MX],lnum;
int wei[MX];
map<pair<int,int>,int>mp;
void init(int a){memset(fst,0xff,sizeof(fst));lnum=-1;mp.clear();n=a;}
{
nxt[++lnum]=fst[nu];
fst[nu]=lnum;
u[lnum]=nu;
v[lnum]=nv;
wei[lnum]=1;
mp[make_pair(nu,nv)]=lnum+100;
}
int vis[MX],vnum;
void dfs(int x,int c)
{
if(vis[x]==c)return;
vis[x]=c;
for(int i=fst[x];i!=-1;i=nxt[i])
if(vis[v[i]]!=c&&wei[i])
dfs(v[i],c);
}
int color()
{
memset(vis,0,sizeof(vis));
vnum=0;
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i,++vnum);
return vnum;
}
void cut(int a,int b)
{
int e=mp[make_pair(a,b)]-100,f=e^1;
if(e<0||wei[e]==0);
else wei[e]--,wei[f]--;
}
void join(int a,int b)
{
int e=mp[make_pair(a,b)]-100,f=e^1;
else wei[e]++,wei[f]++;
}
}g1,g2;
struct qeury
{
char o;
int a,b;
}qur[MQ];
int n,m,q;

void input()
{
int a,b;char ch;
scanf("%d%d",&n,&m);
g1.init(n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
g1.join(a,b);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
ch=getchar();
while(ch!='A'&&ch!='D'&ch!='Q')ch=getchar();
qur[i].o=ch;
if(ch=='A'||ch=='D')scanf("%d%d",&qur[i].a,&qur[i].b);
}
}

void prework()
{
for(int i=1;i<=q;i++)if(qur[i].o=='D')g1.cut(qur[i].a,qur[i].b);
g2.init(g1.color());
for(int i=0;i<=g1.lnum;i+=2)
if(g1.vis[g1.u[i]]!=g1.vis[g1.v[i]])
g2.join(g1.vis[g1.u[i]],g1.vis[g1.v[i]]);
for(int i=1;i<=q;i++)qur[i].a=g1.vis[qur[i].a],qur[i].b=g1.vis[qur[i].b];
}

void work()
{
for(int i=1;i<=q;i++)
{
if(qur[i].o=='A')g2.join(qur[i].a,qur[i].b);
else if(qur[i].o=='D')g2.cut(qur[i].a,qur[i].b);
else printf("%d\n",g2.color());
}
}

int main()
{
input();
prework();
work();
return 0;
}


## 解法二：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#define MX 200005
#define MT 10001
#define mid ((l+r)>>1)
#define ls (a<<1)
#define rs (a<<1|1)

using namespace std;

struct edge
{
int u,v;
bool operator < (const edge a)const
{
if(min(u,v)!=min(a.u,a.v))return min(u,v)<min(a.u,a.v);
else return max(u,v)<max(a.u,a.v);
}
};
struct node
{
int l,r,v;
vector<edge>e;
}tre[MT*4];
map<edge,int>mp;
edge e[MX];
int lnum;
int beg[MX],fin[MX];
int qtm[MT],fa[MX],siz[MX],ccnum;
int n,m,q;

int findfa(int x){return (fa[x]==x?x:findfa(fa[x]));}

void cut(int y){if(y)ccnum++,siz[fa[y]]-=siz[y],fa[y]=y;}

int join(int x,int y)
{
int f1=findfa(x),f2=findfa(y);
if(siz[f1]>siz[f2])swap(f1,f2);
if(f1==f2)return 0;
else
{
ccnum--;
siz[f1]+=siz[f2];
fa[f2]=f1;
return f2;
}
}

void input()
{
int a,b;char ch;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
e[++lnum]=(edge){a,b};
mp[e[lnum]]=lnum;
beg[lnum]=1;
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
ch=getchar();
while(ch!='A'&&ch!='D'&&ch!='Q')ch=getchar();
if(ch=='A')
{
scanf("%d%d",&a,&b);
e[++lnum]=(edge){a,b};
mp[e[lnum]]=lnum;
beg[lnum]=i;
}
else if(ch=='D')
{
scanf("%d%d",&a,&b);
fin[mp[(edge){a,b}]]=i;
mp[(edge){a,b}]=0;
}
else qtm[i]=1;
}
for(int i=1;i<=lnum;i++)if(!fin[i])fin[i]=q;
}

void build(int a,int l,int r)
{
tre[a].l=l,tre[a].r=r;
tre[a].e.clear();
if(l==r)tre[a].v=qtm[l];
else build(ls,l,mid),build(rs,mid+1,r),tre[a].v=tre[ls].v|tre[rs].v;
}

void insrt(int a,int ql,int qr,edge eg)
{
int l=tre[a].l,r=tre[a].r;
if(ql<=l&&r<=qr){if(tre[a].v)tre[a].e.push_back(eg);}
else if(ql>r||qr<l)return;
else insrt(ls,ql,qr,eg),insrt(rs,ql,qr,eg);
}

void dfs(int a)
{
vector<int>tmp;
int l=tre[a].l,r=tre[a].r;
for(int i=0;i<tre[a].e.size();i++)tmp.push_back(join(tre[a].e[i].u,tre[a].e[i].v));
if(l==r)printf("%d\n",ccnum);
else {if(tre[ls].v)dfs(ls);if(tre[rs].v)dfs(rs);}
for(int i=0;i<tre[a].e.size();i++)cut(tmp[i]);
}

int main()
{
input();
for(int i=1;i<=n;i++)siz[i]=1,fa[i]=i;
build(1,1,q);
for(int i=1;i<=lnum;i++)insrt(1,beg[i],fin[i],e[i]);
ccnum=n;
dfs(1);
return 0;
}


### 1 条评论

#### konnyakuxzy · 2018年3月3日 5:22 下午

#include <bits/stdc++.h>

#define NS (5005)
#define QS (10005)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; dig = 0;
while (c = getchar(), !isdigit(c));
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int n, m, q, o[QS], x[QS], y[QS], cur[NS], cnt;

bool g1[NS][NS], book[NS][NS], vis[NS];

char opt[10];

map<int, int> g[NS];

void Init(int a)
{
vis[a] = 1, cur[a] = cnt;
for (int i = 1; i <= n; i += 1)
if (g1[a][i] && !book[a][i] && !vis[i])
Init(i);
}

void dfs(int a)
{
vis[a] = 1;
for (map<int, int>::iterator i = g[a].begin(); i != g[a].end(); i++)
if (!vis[i->first]) dfs(i->first);
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1, a, b; i <= m; i += 1)
IN(a), IN(b), g1[a][b] = g1[b][a] = 1;
IN(q);
for (int i = 1; i <= q; i += 1)
{
scanf("%s", opt);
if (opt[0] == 'Q') o[i] = 0;
else if (opt[0] == 'A') IN(x[i]), IN(y[i]), o[i] = 1;
else
{
IN(x[i]), IN(y[i]), o[i] = 2;
book[x[i]][y[i]] = book[y[i]][x[i]] = 1;
}
}
for (int i = 1; i <= n; i += 1)
if (!vis[i]) cnt += 1, Init(i);
for (int i = 1; i <= n; i += 1)
for (int j = 1; j <= n; j += 1)
if (g1[i][j] && cur[i] != cur[j])
g[cur[i]][cur[j]]++;
for (int i = 1, ans; i <= q; i += 1)
if (!o[i])
{
ans = 0, memset(vis, 0, sizeof(vis));
for (int j = 1; j <= cnt; j += 1)
if (!vis[j]) dfs(j), ans += 1;
printf("%d\n", ans);
}
else if (o[i] == 1)
{
if (cur[x[i]] != cur[y[i]])
g[cur[x[i]]][cur[y[i]]]++, g[cur[y[i]]][cur[x[i]]]++;
}
else
{
if (cur[x[i]] != cur[y[i]])
{
g[cur[x[i]]][cur[y[i]]]--, g[cur[y[i]]][cur[x[i]]]--;
if (!g[cur[x[i]]][cur[y[i]]])
{
g[cur[x[i]]].erase(g[cur[x[i]]].find(cur[y[i]]));
g[cur[y[i]]].erase(g[cur[y[i]]].find(cur[x[i]]));
}
}
}
return 0;
}