题目
给一个\(n\)个点\(m\)条边的无向连通图，\(Q\)次往图中加边，每次加边后问图中的桥有多少个。（加边后边留着）。
\(n\le 10^5,m\le 2\times 10^5,Q\le 10^5\)。
分析
容易发现一条边为桥当且仅当它不在任意一个环中。
于是我们对最开始的图先得到它的生成树，然后把剩下的边加进去，加边的时候把树上两点路径上的点都标记为不是桥。每次询问的时候一样操作。这个东西可以方便地用树链剖分和线段树维护。
时间复杂度为\(O((m-n+Q)\log ^2n)\)。
代码
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define M(x) memset(x,0,sizeof x)
using namespace std;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=1e5+1;
const int maxj=17;
const int maxm=2e5+1;
typedef pair<int,int> Pair;
Pair bian[maxm];
int n,m;
namespace uns {
int f[maxn];
void clear(int n) {for (int i=1;i<=n;++i) f[i]=i;}
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
}
namespace sgt {
int t[maxn<<2];
bool clr[maxn<<2];
void init(int x,int l,int r) {
clr[x]=false;
if (l==r) {
t[x]=(l!=1);
return;
}
int mid=(l+r)>>1;
init(x<<1,l,mid),init(x<<1|1,mid+1,r);
t[x]=t[x<<1]+t[x<<1|1];
}
void pushdown(int x) {
if (!clr[x]) return;
t[x<<1]=t[x<<1|1]=0;
clr[x<<1]=clr[x<<1|1]=true;
clr[x]=false;
}
void clear(int x,int L,int R,int l,int r) {
if (L==l && R==r) {
t[x]=0;
clr[x]=true;
return;
}
pushdown(x);
int mid=(L+R)>>1;
if (r<=mid) clear(x<<1,L,mid,l,r); else
if (l>mid) clear(x<<1|1,mid+1,R,l,r); else
clear(x<<1,L,mid,l,mid),clear(x<<1|1,mid+1,R,mid+1,r);
t[x]=t[x<<1]+t[x<<1|1];
}
void clear(int l,int r) {
clear(1,1,n,l,r);
}
}
namespace tree {
vector<int> g[maxn];
int f[maxn][maxj],dep[maxn],size[maxn],top[maxn],son[maxn];
int first[maxn],second[maxn],dfx;
void add(int x,int y) {g[x].push_back(y);}
void clear(int n) {
M(f),M(dep),M(size),M(top),M(son),M(first),M(second),dfx=0;
for (int i=1;i<=n;++i) g[i].clear();
}
int dfs(int x,int fa) {
f[x][0]=fa;
dep[x]=dep[fa]+1;
int &sz=size[x]=1,&sn=son[x]=0;
for (int v:g[x]) if (v!=fa) {
sz+=dfs(v,x);
if (size[v]>size[sn]) sn=v;
}
}
void Top(int x,int fa,int tp) {
first[x]=++dfx;
top[x]=tp;
if (son[x]) Top(son[x],x,tp);
for (int v:g[x]) if (v!=son[x] && v!=fa) Top(v,x,v);
second[x]=dfx;
}
void run() {
for (int j=1;j<maxj;++j) for (int i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y) {
if (dep[x]<dep[y]) swap(x,y);
for (int j=maxj-1;j>=0;--j) if (dep[f[x][j]]>=dep[y]) x=f[x][j];
if (x==y) return x;
for (int j=maxj-1;j>=0;--j) if (f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j];
return f[x][0];
}
void work(int x,int l) {
for (int y=top[x];dep[y]>dep[l];y=top[x=f[y][0]]) {
sgt::clear(first[y],first[x]);
}
if (dep[x]>dep[l]) sgt::clear(first[l]+1,first[x]);
}
int deal(int x,int y) {
if (dep[x]>dep[y]) swap(x,y);
int l=lca(x,y);
x==l?work(y,x):work(x,l),work(y,l);
return sgt::t[1];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
int cases=0;
while (true) {
n=read(),m=read();
if (!n && !m) break;
printf("Case %d:\n",++cases);
int wat=0;
uns::clear(n);
tree::clear(n);
for (int i=1;i<=m;++i) {
int x=read(),y=read();
int fx=uns::find(x),fy=uns::find(y);
if (fx!=fy) tree::add(x,y),tree::add(y,x),uns::f[fx]=fy; else bian[++wat]=make_pair(x,y);
}
tree::dfs(1,1);
tree::Top(1,1,1);
tree::run();
sgt::init(1,1,n);
for (int i=1;i<=wat;++i) {
int x=bian[i].first,y=bian[i].second;
tree::deal(x,y);
}
int q=read();
while (q--) {
int x=read(),y=read();
int ans=tree::deal(x,y);
printf("%d\n",ans);
}
puts("");
}
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/7172118.html
