Description
A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers. The administrator finds that some links are vital to the network, because failure of any one of them can cause that data can't be transformed between some computers. He call such a link a bridge. He is planning to add some new links one by one to eliminate all bridges.
You are to help the administrator by reporting the number of bridges in the network after each new link is added.
时间是5s，23333；tarjan求桥+朴素LCA
首先想到tarjan求桥，能把桥的个数弄出来，然后考虑修改，每次相当于把两个算个联通分量加上一条边，然后再缩点，再加边。但是不知道怎么处理。
所以直接在tarjan的dfs树上跑两个节点，遇到桥ans--。时间O（q*n）。
tarjan的dfs树感觉是一个很玄学的东西，好像加了一个树形DP，就变成了tarjan。233
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 101000
#define M 501000
using namespace std;
int n,m,tim,q;
int head[N],to[M],nxt[M],cnt;
int fa[N],ans,dfn[N],low[N],deep[N],tot;
bool v[N];
void add(int x,int y)
{
to[cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt++;
}
int read()
{
int re=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
void clear()
{
ans=cnt=0;
memset(head,-1,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(deep,0,sizeof(deep));
memset(v,0,sizeof(v));
}
void tarjan(int x,int pre)
{
dfn[x]=low[x]=++tot;
for(int i=head[x];i!=-1;i=nxt[i])
{
if(i==pre) continue;
int y=to[i];
if(!dfn[y])
{
fa[y]=x;
deep[y]=deep[x]+1;
tarjan(y,i^1);low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
ans++,v[y]=1;
}
else low[x]=min(low[x],dfn[y]);
}
}
int main()
{
n=read();m=read();
while(n!=0||m!=0)
{
tim++;printf("Case %d:\n",tim);
clear();
int x,y;
while(m--)
{
x=read();y=read();
add(x,y);add(y,x);
}
tarjan(1,-1);
q=read();
while(q--)
{
x=read();y=read();
if(deep[x]<deep[y])swap(x,y);
while(deep[x]<deep[y])
{
if(v[x]) v[x]=0,ans--;
x=fa[x];
}
if(x==y) continue;
while(x!=y)
{
if(v[x]) v[x]=0,ans--;
if(v[y]) v[y]=0,ans--;
x=fa[x],y=fa[y];
}
printf("%d\n",ans);
}
puts("");scanf("%d%d",&n,&m);
}
return 0;
}