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.
Input
The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M≤ 200,000).
Each of the following M lines contains two integers A and B ( 1≤ A≠ B ≤ N), which indicates a link between computer A and B. Computers are numbered from 1 to N. It is guaranteed that any two computers are connected in the initial network.
The next line contains a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links the administrator plans to add to the network one by one.
The i-th line of the following Q lines contains two integer A and B(1 ≤ A ≠ B ≤ N), which is the i-th added new link connecting computer A and B.
The last test case is followed by a line containing two zeros.
Output
For each test case, print a line containing the test case number( beginning with 1) and Q lines, the i-th of which contains a integer indicating the number of bridges in the network after the first i new links are added. Print a blank line after the output for each test case.
Sample Input
3 2 1 2 2 3 2 1 2 1 3 4 4 1 2 2 1 2 3 1 4 2 1 2 3 4 0 0
Sample Output
Case 1: 1 0 Case 2: 2 0
本题可以先跑一边tarjan求出所有的割桥
并将所有的强连通分量进行缩点
然后对于每次查询对添加新边的两点和他们到lca的点缩点 并将经过的的所有桥进行标记
但是本体的数据水所以不缩点也能过
直接tarjan时求出其深度优先树形图
我们可以不缩点直接在深度优先树形图中跑lca即可
值得一提的就是我之前用map记录一条边是否为割桥
map key 为边上的两个顶点
但是tle了
仔细一想可以证明 在tarjan中跑出的割桥可以用树的子节点记录
改成数组标记后很容易就过了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
int first[100005];
int nxt[400005];
int to[400005];
int cutline[400005];//桥biaozhi 1biaoshi 能回去
int dfn[100005];
int low[100005];
int dep[100005];
int father[100005];
int hush[100005];
int ans=0;
int id;
struct node
{
int st;
int en;
} a[400005];
void tarjan(int x,int last)
{
if(x!=1) father[x]=last;
dfn[x]=low[x]=++id;
dep[x]=dep[last]+1;
for(int i=first[x]; i!=-1; i=nxt[i])
{
int tmp=to[i];
if(!dfn[tmp])
{
tarjan(tmp,x);
low[x]=min(low[x],low[tmp]);
if(low[tmp]>dfn[x])
{
cutline[i]=1;
cutline[i^1]=1;
ans++;
hush[tmp]=1;//zi fu
}
}
else if(tmp!=last)
{
low[x]=min(low[x],dfn[tmp]);
}
}
return ;
}
void lca (int u,int v)
{
if(dep[u]<dep[v])//让u比较深
{
swap(u,v);
}
while(dep[u]>dep[v])//加到同样深度
{
if(hush[u]==1)
{
hush[u]=0;
ans--;
}
u=father[u];
}
while(u!=v)
{
if(hush[u]==1)
{
hush[u]=0;
ans--;
}
if(hush[v]==1)
{
hush[v]=0;
ans--;
}
u=father[u];
v=father[v];
}
}
int n,m;
int main()
{
//freopen("in.txt","r",stdin);
int cnt=0;
int cas=0;
while(~scanf("%d%d",&n,&m))
{
cas++;
if(n==0&&m==0) break;
int temp1,temp2;
//初始化内容
id=0;
ans=0;
cnt=-1;
memset(hush,0,sizeof(hush));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(first,-1,sizeof(first));
memset(nxt,-1,sizeof(nxt));
memset(cutline,0,sizeof(cutline));
for(int i=1; i<=m; i++)
{
scanf("%d%d",&temp1,&temp2);
cnt++;
nxt[cnt]=first[temp1];
first[temp1]=cnt;
to[cnt]=temp2;
cnt++;
nxt[cnt]=first[temp2];
first[temp2]=cnt;
to[cnt]=temp1;
}
tarjan(1,0);
dep[0]=0;
int q;
scanf("%d",&q);
printf("Case %d:
",cas);
while(q--)
{
scanf("%d%d",&temp1,&temp2);
lca(temp1,temp2);
printf("%d
",ans);
}
printf("
");
}
}