点击打开链接

注意到20w条边，但是询问只有1w，所以有很多边是从头到尾不变的。

首先离线处理，将从未删除的边缩点，缩点后的图的点数不会超过2w，对于每一次add或者delete，直接dfs看是否能从a走到b，然后维护一个ans。

数据不强，不然这种复杂度起码要跑10s。。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 5001
#define M 530005
struct node2
{
    char q;
    int a,b;
}f[200005],Q[10005];
struct node
{
    int v,next;
}edge[M];
int head[N],set[N];
bool d[N][N],v[N];
int e[N][N];
int id,ans;
void add(int a,int b)
{
    edge[id].v=b;
    edge[id].next=head[a];
    head[a]=id++;
}
void init(int n)
{
    memset(head,-1,sizeof(head));
    id=ans=0;
	for(int i=1;i<=n;i++)set[i]=i;
}
int find(int x)
{
    if(x!=set[x]) return set[x]=find(set[x]);
    return set[x];
}
void merge(int x,int y)
{
	set[find(y)]=find(x);
}

bool dfs(int a,int b)
{
    if(a==b) return true;
    for(int i=head[a];~i;i=edge[i].next)
    {
        int to=edge[i].v;
        if(e[a][to]>0&&!v[to])
        {
            v[to]=true;
            if(dfs(to,b)) return true;
        }
    }
    return false;
}
int n;
void addedge(int a,int b)
{
    memset(v,false,sizeof(v));
    if(!dfs(a,b)) ans--;
    e[a][b]++;
    e[b][a]++;
    add(a,b);
    add(b,a);
}
void del(int a,int b)
{
    memset(v,false,sizeof(v));
    e[a][b]--;
    e[b][a]--;
    if(!dfs(a,b)) ans++;
}
inline int ReadInt()
{
    char ch = getchar();
    int data = http://www.mamicode.com/0;>