POJ3694 Network
枫林晚
2018-03-23 11:12:56
题意:
给出一个无向连通图,q次增加后询问,问每次增加后剩余“桥(割边)”的数量。
思路:
先将所有的边双连通分量找到,缩点变成树,找到dcc个数,桥数即为dcc-1;
对于每个询问,若c[x]==c[y]无影响;反之,在树上找到c[x]、c[y]的LCA,再将路上的桥变为0,sum++,最后桥数减去sum。;
代码:
```cpp
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int N=1e5+10;
const int M=2*1e5+10;
struct node{
int nxt,to;
}bian[2*M];
int head[N];
int cnt1=1;
int pre[N],nxt[2*M],to[2*M];
int cnt2=1;
int dfn[N],low[N];
int tot,c[N];
bool bri[2*M];
int fa[N];
int num;
int dcc;
int n,m;
int f[N][30];
int dep[N];
int root;
int L;
bool exi[2*N+10];
void add(int x,int y)
{
bian[++cnt1].nxt=head[x];
bian[cnt1].to=y;
head[x]=cnt1;
}
void add_c(int x,int y)
{
nxt[++cnt2]=pre[x];
to[cnt2]=y;
pre[x]=cnt2;
}
void tarjan(int x,int in)
{
dfn[x]=low[x]=++num;
for(int i=head[x];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(!dfn[y])
{
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
{
bri[i]=bri[i^1]=true;
}
}
else if(i!=(in^1))
{
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(int x)
{
c[x]=dcc;
for(int i=head[x];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(c[y]||bri[i]) continue;
dfs(y);
}
}
void build()
{
for(int i=2;i<=cnt1;i++)
{
int x=bian[i].to;
int y=bian[i^1].to;
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
}
}
void zbb(int x,int d,int fc)
{
dep[x]=d;
for(int i=pre[x];i;i=nxt[i])
{
int y=to[i];
if(y!=fc)
{
f[y][0]=x;
fa[y]=i;
exi[i]=1;
zbb(y,d+1,x);
}
}
}
void father()
{
dep[0]=-1;
dep[1]=0;
for(int i=pre[1];i;i=nxt[i])
{
int y=to[i];
f[y][0]=1;
fa[y]=i;
exi[i]=1;
zbb(y,1,1);
}
for(int i=1;i<=30;i++)
{
if((2<<i)>n)
{
L=i-1;break;
}
}
for(int j=1;j<=L;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=L;j>=0;j--)
{
if(dep[f[x][j]]>=dep[y])
x=f[x][j];
}
if(x==y) return x;
for(int j=L;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 end)
{
if(x==end) return;
int bb=-5;
int sum=0;
while(bb!=end)
{
bb=f[x][0];
if(exi[fa[x]])
{
exi[fa[x]]=0;
sum++;
}
x=bb;
}
dcc-=sum;
}
void clear()
{
memset(to,0,sizeof to);
memset(pre,0,sizeof pre);
memset(nxt,0,sizeof nxt);
memset(bri,0,sizeof bri);
memset(bian,0,sizeof (struct node)*2*M);
memset(head,0,sizeof head);
cnt1=1;cnt2=1;
num=0;tot=0;dcc=0;
root=1;L=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(fa,0,sizeof fa);
memset(f,0,sizeof f);
memset(dep,0,sizeof dep);
memset(c,0,sizeof c);
memset(exi,0,sizeof exi);
}
int main()
{
int shu=0;
while(1)
{
scanf("%d%d",&n,&m);
if(n==0&&m==0) break;
shu++;
clear();
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
tarjan(1,0);
for(int i=1;i<=n;i++)
{
if(!c[i])
{
dcc++;
dfs(i);
}
}
build();
father();
dcc--;
int q;
scanf("%d",&q);
bool flag=0;
printf("Case %d:\n",shu);
for(int k=1;k<=q;k++)
{
scanf("%d%d",&x,&y);
if(c[x]==c[y])
{
flag=1;
}
else{
int p=lca(c[x],c[y]);
work(c[x],p);
work(c[y],p);
}
printf("%d\n",dcc);
}
puts("");
}
return 0;
}
```
注意:memset要清空,dep[0]=-1;