Network (POJ 3694)
Network (POJ 3694)
Time Limit: 5000 MS Memory Limit: 64 MB
Problem 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.
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
题目大意
给定一张N个点M条边的无向连通图（可能有重边），然后执行Q次操作，每次向图中添加一条边，并且询问当前无向连通图中桥的数量。 (N≤10^5,M≤2x10^5,Q≤1000)
Solution
边双连通分量的缩点+LCA。
首先把这张无向图进行边双连通分量的缩点，变成一棵树，然后这棵树的边数就是桥的数量。对于加边和询问操作，若添加一条连接结点u、v的边，若u、v在同一个边双连通分量中，则该操作对图中桥的数量没有影响。若u、v不在同一个双连通分量中，则树上u、v的路径闭合成一个环，该环上的所有边都不再是桥。我们求出u、v的LCA，然后分别从u、v走到LCA，标记经过的每一条边已经不是桥，同时修改整张图的桥的数量。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct edge{int next,to;};
edge G[400010];
int head[100005]={0};
edge EDCCG[400010]={0};
int EDCC_head[100005]={0};
int EDCC[100005]={0};
int DFN[100005]={0};
int LOW[100005]={0};
int deep[100005]={0};
int anc[100005][21]={0};
int fa[100005]={0};
bool Bridge[400005]={0};
bool EDCC_Bridge[400005]={0};
int N,M,cnt=2,EDCC_cnt=2,Index=0,EDCC_Index=0,Bridge_Count=0;
inline void add_edge(int u,int v){
G[cnt].to=v;
G[cnt].next=head[u];
head[u]=cnt++;
return;
}
inline void add_edge_EDCC(int u,int v){
EDCCG[EDCC_cnt].to=v;
EDCCG[EDCC_cnt].next=EDCC_head[u];
EDCC_Bridge[EDCC_cnt]=true;
EDCC_head[u]=EDCC_cnt++;
return;
}
void Tarjan(int u,int In_Edge){
DFN[u]=LOW[u]=++Index;
for(register int i=head[u];i;i=G[i].next){
if(!DFN[G[i].to]){
Tarjan(G[i].to,i);
LOW[u]=min(LOW[u],LOW[G[i].to]);
if(DFN[u]<LOW[G[i].to])
Bridge[i]=Bridge[i^1]=true;
}
else if(i!=(In_Edge^1))
LOW[u]=min(LOW[u],DFN[G[i].to]);
}
return;
}
void DFS(int u){
EDCC[u]=EDCC_Index;
for(register int i=head[u];i;i=G[i].next){
if(EDCC[G[i].to] || Bridge[i]) continue;
DFS(G[i].to);
}
return;
}
void DFS_Init(int u){
anc[u][0]=fa[u];
for(register int i=1;i<=20;i++)
anc[u][i]=anc[anc[u][i-1]][i-1];
for(register int i=EDCC_head[u];i;i=EDCCG[i].next){
if(EDCCG[i].to!=fa[u]){
fa[EDCCG[i].to]=u;
deep[EDCCG[i].to]=deep[u]+1;
DFS_Init(EDCCG[i].to);
}
}
return;
}
int LCA(int u,int v){
if(u==1 || v==1) return 1;
if(deep[u]<deep[v]) swap(u,v);
for(register int i=20;i>=0;i--)
if(deep[v]<=deep[anc[u][i]])
u=anc[u][i];
if(u==v) return u;
for(register int i=20;i>=0;i--)
if(anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];}
return anc[u][0];
}
inline void Init(){
memset(DFN,0,sizeof(DFN));
memset(LOW,0,sizeof(LOW));
memset(head,0,sizeof(head));
memset(EDCC,0,sizeof(EDCC));
memset(EDCC_head,0,sizeof(EDCC_head));
memset(Bridge,0,sizeof(Bridge));
memset(EDCC_Bridge,0,sizeof(EDCC_Bridge));
memset(deep,0,sizeof(deep));
memset(anc,0,sizeof(anc));
memset(fa,0,sizeof(fa));
cnt=2;EDCC_cnt=2;Index=0;EDCC_Index=0;Bridge_Count=0;
return;
}
void Maintain(int u,int ANC){
if(u==ANC) return;
for(register int i=EDCC_head[u];i;i=EDCCG[i].next){
if(EDCCG[i].to==fa[u]){
if(EDCC_Bridge[i]==true) --Bridge_Count;
EDCC_Bridge[i]=EDCC_Bridge[i^1]=false;
Maintain(EDCCG[i].to,ANC);
}
}
return;
}
int main(){
int Case=0;
while(~scanf("%d %d",&N,&M)){
if(N==M && N==0) break;
++Case;
printf("Case %d:\n",Case);
Init();
for(register int i=1;i<=M;i++){
int u,v;
scanf("%d %d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
Tarjan(1,0);
for(register int i=1;i<=N;i++)
if(!EDCC[i]){++EDCC_Index;DFS(i);}
for(register int i=2;i<cnt;i++){
int u=G[i].to,v=G[i^1].to;
if(EDCC[u]==EDCC[v]) continue;
add_edge_EDCC(EDCC[u],EDCC[v]);
}
Bridge_Count=EDCC_Index-1;
DFS_Init(1);
int Q;
scanf("%d",&Q);
while(Q--){
int u,v;
scanf("%d %d",&u,&v);
if(EDCC[u]==EDCC[v]){printf("%d\n",Bridge_Count);continue;}
int p=LCA(EDCC[u],EDCC[v]);
Maintain(EDCC[u],p);
Maintain(EDCC[v],p);
printf("%d\n",Bridge_Count);
}
}
return 0;
}