分析
考虑求出边双连通分量,那么题目其实就是在问,有多少个桥。那么由于边双缩点之后,整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离,在将这个链上的权值变为 。这个考虑树链剖分或者 维护,写完才发现,好像直接并查集时间复杂度好像还要更优。这里采用了 实现,时间总复杂度为 。
代码
#include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();} return f ? -x : x; } const int N = 4e5 + 1000; struct Lct { bool r[N]; int val[N],sum[N],ch[N][2],tag[N],fa[N]; void pushr(int x) {swap(ch[x][1],ch[x][0]);r[x] ^= 1;} bool nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;} void pushup(int x) {sum[x] = (val[x] + sum[ch[x][0]] + sum[ch[x][1]]);} void pusha(int x) {sum[x] = val[x] = 0;tag[x] = 1;} void pushdown(int x) { if(r[x]) {if(ch[x][0]) pushr(ch[x][0]);if(ch[x][1]) pushr(ch[x][1]);r[x] = 0;} if(tag[x]) {if(ch[x][0]) pusha(ch[x][0]);if(ch[x][1]) pusha(ch[x][1]);tag[x] = 0;} } void push(int x) {if(nroot(x))push(fa[x]);pushdown(x);} void rotate(int x) { int y = fa[x],z = fa[y],k = (ch[y][1] == x),w = ch[x][!k]; if(nroot(y)) ch[z][ch[z][1] == y] = x;ch[y][k] = w;ch[x][!k] = y; if(w) fa[w] = y;fa[x] = z;fa[y] = x;pushup(y); } void splay(int x) { push(x);while(nroot(x)) { int y = fa[x],z = fa[y]; if(nroot(y)) rotate(((ch[z][1]==y)^(ch[y][1]==x))?y:x); rotate(x);pushup(x); } } void access(int x) {for(int y = 0;x;x = fa[y=x])splay(x),ch[x][1]=y,pushup(x);} void makeroot(int x) {access(x);splay(x);pushr(x);} void split(int x,int y) {makeroot(x);access(y);splay(y);} void link(int x,int y) {split(x,y);fa[x] = y;} int ask(int x,int y) {split(x,y);int ans = sum[y];pusha(y);return ans;} void clear(int tot) {for(int x=0;x<=tot;x++)ch[x][1]=ch[x][0]=tag[x]=val[x]=sum[x]=r[x]=fa[x]=0;} }t; int low[N],dfn[N],dcc[N],vis[N],st[N],top,n,m,tot,Dfn,Dcc; vector<int> G[N],id[N]; void tarjan(int x,int fa) { low[x] = dfn[x] = ++Dfn; st[++top] = x;vis[x] = 1; for(int i = 0 ;i < G[x].size();i++) { if(id[x][i] == fa) continue;int y = G[x][i]; if(!dfn[y]) tarjan(y,id[x][i]),low[x] = min(low[x],low[y]); else if(vis[y]) low[x] = min(dfn[y],low[x]); } if(low[x] == dfn[x]) { Dcc++;dcc[x] = Dcc;vis[x] = 0; while(st[top] != x) { dcc[st[top]] = Dcc;vis[st[top]] = 0; top--; } top--; } } int main() { int Case = 0; while(1) { n = read();m = read(); if(n == 0 && m == 0) break;printf("Case %d:\n",++Case); t.clear(tot);tot = 0;Dfn = 0,Dcc = 0;top = 0; for(int i = 1;i <= n;i++) { G[i].clear();id[i].clear(); st[i] = vis[i] = low[i] = dfn[i] = dcc[i] = 0; } for(int i = 1;i <= m;i++) { int u = read(),v = read(); G[u].push_back(v);G[v].push_back(u); id[u].push_back(i);id[v].push_back(i); } for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i,0); tot = Dcc; for(int x = 1;x <= n;x++) { for(auto y : G[x]) { if(x > y) continue; if(dcc[y] == dcc[x]) continue; ++tot;t.val[tot] = 1; t.link(dcc[y],tot); t.link(dcc[x],tot); } } int Q = read(),res = 0; while(Q--) { int x = read(),y = read(); if(dcc[x] != dcc[y]) res += t.ask(dcc[x],dcc[y]); printf("%d\n",Dcc - res - 1); } printf("\n"); } }