Network

题目大意

给你一个无向连通图，再给出一些添边操作，询问每次添边操作之后图中还剩下多少桥。

Solution

其实很水，缩个点，然后此时图是一棵树，其中每条边都是割边，然后每次加边就把左右端点路径上的所有边都变成非割边即可

树剖维护一下。放这个题的原因就是码量大了一点。

upd：有一个码量很小的生成树的做法。。。我哭了

code:

#include<bits/stdc++.h>using namespace std;struct qwq{ int v; int nxt;}edge[400010];int cnt=-1;int head[200010];void add(int u,int v){ edge[++cnt].nxt=head[u]; edge[cnt].v=v; head[u]=cnt;}struct tarj{ int ind; int dfn[200010]; int low[200010]; int col[200010]; bool vis[200010]; int stk[200010]; int top; int tot; int x[200010],y[200010]; void init(){ ind=0; tot=0; top=0; memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(col,0,sizeof(col)); memset(vis,0,sizeof(vis)); } void tarjan(int u,int fa){ dfn[u]=low[u]=++ind; stk[++top]=u; vis[u]=true; for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==fa)continue; if(vis[v]){ low[u]=min(low[u],dfn[v]); } else if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); } } if(dfn[u]==low[u]){ tot++; int v; do{ v=stk[top]; top--; col[v]=tot; }while(u!=v); } }}a;int siz[200010];int top[200010];int son[200010];int fa[200010];int tid[200010];int dep[200010];void dfs1(int u,int fath,int depth){ fa[u]=fath; dep[u]=depth; siz[u]=1; for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==fath)continue; dfs1(v,u,depth+1); siz[u]+=siz[v]; if(!son[u]||siz[v]>siz[son[u]])son[u]=v; }}int tim;void dfs2(int u,int topf){ top[u]=topf; tid[u]=++tim; if(son[u])dfs2(son[u],topf); for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==fa[u]||v==son[u])continue; dfs2(v,v); }}int sum[400010];int tag[400010];void build(int o,int l,int r){ tag[o]=0; if(l==r){ sum[o]=1; return; } int mid=(l+r)/2; build(o*2,l,mid); build(o*2+1,mid+1,r); sum[o]=sum[o*2]+sum[o*2+1];}void pushdown(int o){ if(tag[o]){ sum[o*2]=sum[o*2+1]=0; tag[o*2]=tag[o*2+1]=1; tag[o]=0; }}void update(int o,int l,int r,int L,int R){ if(L>R)return; if(L<=l&&r<=R){ tag[o]=1,sum[o]=0; return; } pushdown(o); int mid=(l+r)/2; if(L<=mid)update(o*2,l,mid,L,R); if(mid<R)update(o*2+1,mid+1,r,L,R); sum[o]=sum[o*2]+sum[o*2+1];}int query(int o,int l,int r,int L,int R){ if(L>R)return 0; if(L<=l&&r<=R){ return sum[o]; } pushdown(o); int mid=(l+r)/2; int ret=0; if(L<=mid)ret+=query(o*2,l,mid,L,R); if(mid<R)ret+query(o*2+1,mid+1,r,L,R); return ret;}void updatetree(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); update(1,1,a.tot,tid[top[x]],tid[x]); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,a.tot,tid[x]+1,tid[y]);}int main(){ memset(head,-1,sizeof(head)); int n,m; int cas=0; while(scanf("%d%d",&n,&m)&&n&&m){ printf("Case %d:\n",++cas); a.init(); tim=0; memset(siz,0,sizeof(siz)); memset(top,0,sizeof(top)); memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(tid,0,sizeof(tid)); memset(dep,0,sizeof(dep)); memset(head,-1,sizeof(head)); cnt=-1; for(int i=1;i<=m;++i){ int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); a.x[i]=u,a.y[i]=v; } for(int i=1;i<=n;++i){ if(!a.vis[i])a.tarjan(i,-1); } memset(head,-1,sizeof(head)); cnt=-1; for(int i=1;i<=m;++i){ if(a.col[a.x[i]]!=a.col[a.y[i]]){ add(a.col[a.x[i]],a.col[a.y[i]]); add(a.col[a.y[i]],a.col[a.x[i]]); } } dfs1(1,0,1); dfs2(1,1); build(1,1,a.tot); int q; scanf("%d",&q); for(int i=1;i<=q;++i){ int u,v; scanf("%d%d",&u,&v); updatetree(a.col[u],a.col[v]); printf("%d\n",sum[1]-1); } puts(""); } }