题意:
给出一张无向图,q个询问每个询问给出两个点xy,输出在xy之间添加一条边之后整张图的割边数量(每个询问都基于前一个询问…)
分析:
今天刚知道怎么求割边
当然这道题就更加简单了一点,不需要知道哪些边是割边,只需要知道数量就可以,所以我们可以tarjan缩点,缩完点之后变成了一棵树,树边就是桥…
在两个点xy之间添加一条边,如果xy缩完点属于同一个点那么割边数目不变,如果不是就暴力的往上走到两个点的lca,这个过程中经过的边就不是割边了…所以我们就把经过的点都缩到lca这个点上…
代码如下:
#include#include #include #include //by NeighThorn using namespace std; const int maxn=100000+5,maxm=200000+5; int n,m,q,hd[maxn],to[maxm*2],nxt[maxm*2],edge[maxm*2],cnt,ans,cas; int dfn[maxn],low[maxn],tim,stk[maxn],tail,bel[maxn],fa[maxn],dep[maxn]; inline int read(void){ char ch=getchar();int x=0; while(!(ch>='0'&&ch<='9')) ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } inline void add(int x,int y){ to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++; } inline void tarjan(int root,int f){ low[root]=dfn[root]=++tim;stk[++tail]=root; for(int i=hd[root];i!=-1;i=nxt[i]) if(i!=f){ if(!dfn[to[i]]) tarjan(to[i],i^1),low[root]=min(low[root],low[to[i]]); else low[root]=min(low[root],dfn[to[i]]); } if(low[root]==dfn[root]){ int tmp;ans++; do{ tmp=stk[tail--];bel[tmp]=root; }while(tmp!=root); } } inline int find(int x){ return bel[x]==x?x:bel[x]=find(bel[x]); } inline void dfs(int root,int f){ fa[root]=f; for(int i=hd[root];i!=-1;i=nxt[i]) if(!dep[to[i]]) dep[to[i]]=dep[root]+1,dfs(to[i],root); } inline void lca(int x,int y){ while(x!=y){ ans--; if(dep[x]>dep[y]) x=bel[x]=find(fa[x]); else y=bel[y]=find(fa[y]); } } signed main(void){cas=0; while(scanf("%d%d",&n,&m)&&!(!n&&!m)){ tim=cnt=ans=tail=0; memset(hd,-1,sizeof(hd)); memset(dep,0,sizeof(dep)); memset(dfn,0,sizeof(dfn)); for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x); for(int i=1;i<=n;i++) bel[i]=i; tarjan(1,-1);dep[1]=1;dfs(1,1);q=read();ans--; printf("Case %d:\n",++cas); for(int i=1,x,y;i<=q;i++){ x=read();y=read(); int fx=find(x),fy=find(y); if(fx==fy) printf("%d\n",ans); else lca(fx,fy),printf("%d\n",ans); } } return 0; }