POJ3694(Network)

Network

题目传送门

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

Case 2:

2

思路

Tarjan割边 + LCA

首先对整个图做一次Tarjan需要记录：当前节点的父节点，割边数目，哪两个点对形成的是割边。然后每次加入一条边，这条边的两个点到他们的LCA点这部分是一颗小树。由于这条边的加入会使这棵树成环。所以这个小树中的割边全部都会消失。将割边的标记取消就好，割边数减一，最后输出。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 1e5+5;
struct edge{
	int to;
	int next;
}e[maxn*4];
int head[maxn];
int dfn[maxn];			//时间戳 
int low[maxn];			//返祖时间序 
bool cut[maxn]; 		//割边 
int f[maxn];			//父节点 
int tot,cnt,ans;		
inline void addedge(int x,int y)
{
	e[tot].to = y;
	e[tot].next = head[x];
	head[x] = tot++;
}
inline void clear_set()
{
	tot = cnt = ans = 0;
	memset(head,-1,sizeof(head));
	memset(low,0,sizeof(low));
	memset(cut,false,sizeof(cut));
	memset(dfn,0,sizeof(dfn));
	for(int i = 0;i < maxn;i++){
		f[i] = i;
	}
}
inline void tarjan(int x,int fx)
{
	dfn[x] = low[x] = ++cnt;
	int k = 0;
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(fx == y && !k){			//忽略反向边一次 
			k++;
			continue;
		}
		if(!dfn[y]){
			f[y] = x;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if(low[y] > dfn[x]){
				ans++;
				cut[y] = true;
			}
		}
		else if(dfn[y] < dfn[x]){
			low[x] = min(low[x],dfn[y]);
		}
	}
}
void LCA(int x,int y)
{
	if(dfn[x] < dfn[y])		swap(x,y);
	while(dfn[x] > dfn[y]){			//x,y跳到同样的深度 
		if(cut[x]){
			cut[x] = false;
			ans--;
		}
		x = f[x];
	}
	while(x != y){				//同时上跳，跳到LCA结束 
		if(cut[x]){		cut[x] = false;	ans--;}
		if(cut[y]){		cut[y] = false;	ans--;}
		x = f[x];y = f[y];
	}
}
int main()
{
	int n,m,q,k = 1;
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0)	break;
		clear_set();
		int x,y;
		for(int i = 0;i < m;i++){
			scanf("%d%d",&x,&y);
			addedge(x,y);	addedge(y,x);
		}
		tarjan(1,-1);
		printf("Case %d:\n",k++);
		scanf("%d",&q);
		while(q--){
			scanf("%d%d",&x,&y);
			LCA(x,y);
			printf("%d\n",ans);
		}
	}
	return 0;
} 
           

愿你走出半生，归来仍是少年~