科学家最近发现了一种高分子有机化合物 SHTSC。这种物质的分子由单个或多个原子组成,原子之间通过化学键相互连接。SHTSC 十分不稳定,其原子之间的化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。
然而,令科学家们大为惊异的是,SHTSC 在变化过程中始终保持着一种特殊的性质:即不存在这样的原子序列 a1,a2,...,an(n>3)满足 a1 与 a2、a2 与
a3、......、an-1 与 an 以及 an 与 a1 都通过化学键相连,但它们之间却没有其他化学键相连的情况。现在科学家将 SHTSC 的原子由 1 到 n 标号,并告诉你
SHTSC 的初始形态以及原子之间的化学键变化情况,他们想知道在实验过程中的某些时刻 SHTSC 分裂成了多少个分子?
第一行两个整数:n, m。表示 SHTSC 的总原子个数以及初始的化学键数。
从第二行开始的 m 行,每行两个整数 a, b (1≤a,b≤n)。表示编号为 a, b 的两
个原子在初始状态中有化学键相连。数据保证每对 a, b 只出现一次。
第 m+2 行有一个整数:q。表示实验的总操作数。
之后 q 行中的每一行为以下三种操作当中的一种:
1、A i j 表示 i 号原子与 j 号原子之间形成了一条新的化学键;
2、D i j 表示 i 号原子与 j 号原子之间原有的化学键断裂了;
3、Q 询问当前 SHTSC 分裂成了多少个不同的分子。
数据保证所有的实验操作都是合法的。
对于每个 Q 操作,输出一行一个整数,为相应时刻的分子个数。
对于 100%的数据, n≤5000,m≤200000,q≤10000。
The Solution
又是SHOI的题，作为一个一天一题选手，在我来看今天的这道题算是比较仁慈的了。
对于题目中给的操作A连边，D断边，Q询问有多少独立联通块。
我们可以这样处理
对于A x，y 我们可以暴力判断x,y连边前是否联通，若不联通则Ans --；
对于D x,y我们依然可以暴力判断x，y断开之后是否联通，若联通则Ans ++;
然后我们跑几遍DFS就好了
注意要用记忆化标记。
这次数据比较水，我比赛时忘记清空标记数组都有70分。ε=(´ο｀*)))唉。。
害我还调了那么久，最后肉眼检查才发现那个小错误。
CODE
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define fd(i,a,b) for (int i=a;i>=b;i--)
#define M 500005
#define N 5005
using namespace std;
int read(int &n)
{
char ch = ' ';
int q = 0, w = 1;
for (;(ch != '-') && ((ch < '0') || (ch> '9'));ch = getchar());
if (ch == '-') w = -1,ch = getchar();
for (; ch >= '0' && ch <= '9';ch = getchar()) q = q * 10 + ch - 48;
n = q * w;
return n;
}
int n,m;
/*struct Edge
{
int to,next;
Edge(void){}
Edge(int a,int b) : to(a),next(b){}
}E[M];*/
int Final[M],Dad[N],c[N][N],Ans;
bool Mark[N],d[N][N];
struct node
{
int x,y;
char c;
}a[M],b[100005];
struct edge
{
int to,from;
};
vector <edge> V;
vector <int> g[N];
/*void Link(int x,int y)
{
E[++ tot] = Edge(y,Final[x]),Final[x] = tot;
E[++ tot] = Edge(x,Final[y]),Final[y] = tot;
}*/
int cnt = 0;
int Get(int x)
{
if (Dad[x] == x) return x;
else return Dad[x] = Get(Dad[x]);
}
bool Dfs(int x,int y)
{
if (x == y) return true;
for (int i = 0;i < g[x].size();i ++)
{
edge e = V[g[x][i]];
if (! Mark[e.to] && c[x][e.to] > 0)
{
Mark[e.to] = true;
if (Dfs(e.to,y)) return true;
}
}
/* for (int k = Final[x];k;k = E[k].next)
{
if (! Mark[E[k]. to] && c[x][E[k].to] > 0)
{
Mark[E[k].to] = true;
if (Dfs(E[k].to,y)) return true;
}
}*/
return false;
}
void Add(int x,int y)
{
memset(Mark,0,sizeof(Mark));
if (!Dfs(x,y)) Ans --;
c[x][y] ++;
c[y][x] ++;
/*tot = 0;
memset(Final,0,sizeof(Final));
memset(E,0,sizeof(E));
Link(x,y);*/
edge e;
e.from = x,e.to = y;
V.push_back(e);
e.from = y,e.to = x;
V.push_back(e);
int tot = V.size();
g[x].push_back(tot - 2);
g[y].push_back(tot - 1);
return;
}
void Del(int x,int y)
{
memset(Mark,false,sizeof(Mark));
c[x][y] --,c[y][x] --;
if (!Dfs(x,y)) Ans ++;
return;
}
int main()
{
freopen("compound.in","r",stdin);
freopen("compound.out","w",stdout);
read(n),read(m);
fo(i,1,n) Dad[i] = i;
fo(i,1,m)
read(a[i].x),read(a[i].y);
int p;
read(p);
fo(i,1,p)
{
scanf("%s",&b[i].c);
if (b[i].c == 'Q') continue;
read(b[i].x),read(b[i].y);
if (b[i].c == 'D') d[b[i].x][b[i].y] = d[b[i].y][b[i].x] = true;
}
fo(i,1,m)
{
int x = a[i].x,y = a[i].y;
if (d[x][y] == true || d[y][x] == true) continue;
x = Get(x), y = Get(y);
if (x != y) Dad[x] = y;
}
fo(i,1,n) if ((Dad[i] = Get(i)) == i) Ans ++;
fo(i,1,m)
{
int x = a[i].x,y = a[i].y;
if (Dad[x] != Dad[y]) Add(Dad[x],Dad[y]);
}
fo(i,1,p)
{
int x = b[i].x, y = b[i].y;
if (b[i].c == 'Q') printf("%d\n",Ans);
else if (b[i].c == 'D') Del(Dad[x],Dad[y]);
else Add(Dad[x],Dad[y]);
}
}