Description:

给定一个图，每次删除一条边或查询两点之间桥的数目，保证任意时刻图联通

$ 1 \le N \le 30000 $ $ 1 \le M \le 100000 $ $ 1 \le Q \le 40000 $

Solution:

离线处理倒序加边， $ LCT $ 维护边双连通分量，在加边时如果已经形成了一个环，就取出环递归将它缩成一个点，如果新加的边两点已经联通，就将一个点 $makeroot$ ，另一个点 $access$ ，得到的辅助树即为这个环，缩点的过程用一个并查集来维护缩点后的点，在输出时桥的个数就是路径上点的个数-1

注意在 $access$ 时循环里 $ k = t[k].fa $ 要改成 $ k = t[k].fa = find(t[k].fa) $ 因为此时 $ t[k].fa $ 已经被替换成了 $ find(t[k].fa) $ 所以在跳的时候顺便修改

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<map>

#include<cstring>

using namespace std;

int read(){

    int res = 0,f;

    char c = getchar();

    while(!isdigit(c) && c != '-')c = getchar();

    if(c == '-'){f = -1;c = getchar();}

    else f = 1;

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

int n,m,q = 0;

#define MAXN 30010

#define MAXM 100010

#define MAXQ 40010

int f[MAXN];

int find(int x){return (x == f[x] ? x : (f[x] = find(f[x])));}

struct node

{

    int c[2],fa,siz;

    bool rev;

    node(){c[0] = c[1] = fa = 0;rev = false;}

}t[MAXN];

void maintain(int rt)

{

    t[rt].siz = 1;

    if(t[rt].c[0] != 0)t[rt].siz += t[t[rt].c[0]].siz;

    if(t[rt].c[1] != 0)t[rt].siz += t[t[rt].c[1]].siz;

    return;

}

bool isroot(int rt){return (t[t[rt].fa].c[0] != rt && t[t[rt].fa].c[1] != rt);}

int id(int rt){return (t[t[rt].fa].c[0] == rt ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void pushdown(int rt)

{

    if(!t[rt].rev)return;

    t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

    swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

    return;

}

void rotate(int x)

{

    int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

    if(!isroot(y))t[z].c[fy] = x;

    t[x].fa = z;

    connect(t[x].c[fx^1],y,fx);

    connect(y,x,fx^1);

    maintain(y);maintain(x);

    return;

}

stack<int> s;

void splay(int x)

{

    s.push(x);

    for(int i = x;!isroot(i);i = t[i].fa){s.push(t[i].fa);}

    while(!s.empty()){pushdown(s.top());s.pop();}

    while(!isroot(x))

    {

        int y = t[x].fa;

        if(isroot(y)){rotate(x);break;}

        if(id(x) == id(y)){rotate(y);rotate(x);}

        else{rotate(x);rotate(x);}

    }

    return;

}

void access(int k){for(int i = 0;k != 0;i = k,k = t[k].fa = find(t[k].fa)){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int x,int y){makeroot(x);makeroot(y);t[x].fa = y;return;}

int root(int x){access(x);splay(x);while(true){pushdown(x);if(t[x].c[0] != 0)x = t[x].c[0];else return x;}}

void pre(int x,int y){makeroot(x);access(y);splay(y);return;}

struct line

{

    int u,v;

    bool tag;

}l[MAXM];

map<pair<int,int>,bool> p;

struct question

{

    int type,u,v;   

}r[MAXQ];

void remove(int rt,int tp)

{

    if(rt == 0)return;

    f[rt] = tp;

    remove(t[rt].c[0],tp);remove(t[rt].c[1],tp);

    t[rt].c[0] = t[rt].c[1] = 0;

    return;

}

void merge(int x,int y)

{

    if(x == y)return;

    if(root(x) != root(y)){link(x,y);return;}

    else{makeroot(x);access(y);splay(x);remove(x,x);maintain(x);}

    return;

}

int ans[MAXQ];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)f[i] = i;

    for(int i = 1;i <= m;++i)

    {

        l[i].u = read();l[i].v = read();if(l[i].u > l[i].v)swap(l[i].u,l[i].v); 

        p[make_pair(l[i].u,l[i].v)] = p[make_pair(l[i].v,l[i].u)] = true;

    }

    int a;

    while(true)

    {

        scanf("%d",&a);if(a == -1)break;r[++q].type = a;

        scanf("%d%d",&r[q].u,&r[q].v);if(r[q].u > r[q].v)swap(r[q].u,r[q].v);

        if(a == 0)p[make_pair(r[q].u,r[q].v)] = p[make_pair(r[q].v,r[q].u)] = false;

    }

    for(int i = 1;i <= m;++i)if(p[make_pair(l[i].u,l[i].v)])merge(find(l[i].u),find(l[i].v));

    for(int i = q;i >= 1;--i)

    {

        r[i].u = find(r[i].u);r[i].v = find(r[i].v);

        if(r[i].type == 0)merge(r[i].u,r[i].v);

        else

        {

            if(r[i].u == r[i].v){ans[i] = 0;continue;}

            pre(r[i].u,r[i].v);

            ans[i] = t[r[i].v].siz - 1;

        }

    }

    for(int i = 1;i <= q;++i)if(r[i].type == 1)printf("%d\n",ans[i]);

    return 0;

}