【POJ - 3694】Network（对dfn求lca 或 缩点+lca 或 边双连通+并查集）

题干：

网络管理员管理大型网络。该网络由N台计算机和成对计算机之间的M链路组成。任何一对计算机都通过连续的链接直接或间接连接，因此可以在任何两台计算机之间转换数据。管理员发现某些链接对网络至关重要，因为任何一个链接的故障都可能导致某些计算机之间无法转换数据。他把这种联系称为桥梁。他计划逐一添加一些新链接以消除所有桥梁。 您将通过在添加每个新链接后报告网络中的网桥数来帮助管理员。

输入

输入包含多个测试用例。每个测试用例以包含两个整数N（1≤N≤100,000）和M（N-1≤M≤200,000）的行开始。 以下M行中的每一行包含两个整数A和B（1≤A≠B≤N），表示计算机A和B之间的链接。计算机编号从1到N.保证任何两台计算机都连接在一起最初的网络。 下一行包含一个整数Q（1≤Q≤1,000），这是管理员计划逐个添加到网络的新链接数。 以下Q行的第i行包含两个整数A和B（1≤A≠B≤N），这是连接计算机A和B的第i个新链接。 最后一个测试用例后跟一行包含两个零的行。

输出

对于每个测试用例，打印一行包含测试用例编号（以1开头）和Q行，其中第i行包含一个整数，表示添加第一个i新链接后网络中的网桥数。在每个测试用例的输出后打印一个空行。

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

题目大意：

   给了一个连通图。 问加入边的过程中，桥的个数。

解题报告：

  在线维护桥的个数就可以了。注意缩点的使用。

AC代码1：（对dfn求lca+暴力）（1157ms）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Edge {
	int u,v;
	int ne;
} e[MAX<<1];
int dfn[MAX],low[MAX],clk;
int head[MAX],tot,fa[MAX];
int qiao[MAX];
int n,m,ans;
void init() {
	for(int i = 1; i<=n; i++) {
		dfn[i]=low[i]=qiao[i]=fa[i]=0;//如果不初始化fa？？？
		head[i] = -1;
	}
	tot = 0;
	clk = 0;
	ans = 0;
}
void add(int u,int v) {
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].ne = head[u];
	head[u] = tot;
}
void tarjan(int x,int rt) {//注意这里fa和rt是不一样的含义！！
	dfn[x] = low[x] = ++clk;
	fa[x] = rt;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].v;
		if(v == rt) continue;
		if(dfn[v] == 0) {
			tarjan(v,x);
			low[x] = min(low[x],low[v]);
			if(low[v] > dfn[x]) {
				qiao[v] = 1;
				ans++;
			}
		} else low[x] = min(low[x],dfn[v]);
	}
}
void lca(int u, int v) {
	while(dfn[v] > dfn[u]) {
		if(qiao[v]) ans--;
		qiao[v] = 0;
		v = fa[v];
	}
	while(dfn[u] > dfn[v]) {
		if(qiao[u]) ans--;
		qiao[u] = 0;
		u = fa[u];
	}
	while(u != v) {
		if(qiao[u]) ans--;
		if(qiao[v]) ans--;
		qiao[u] = qiao[v] = 0;
		u = fa[u];
		v = fa[v];
	}
}
int main() 
{
	int a,b,iCase=0;
	while(~scanf("%d%d",&n,&m)) {
		if(n == 0 && m == 0) break;
		init();
		for(int i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b); add(b,a);
		}
		tarjan(1,0);
		int q;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%d%d",&a,&b);
			lca(a,b);
			printf("%d\n", ans);
		}
		printf("\n");
	}
	return 0 ;
}

其实对上面这个代码的lca函数，做了很多无用的工作，因为u和v最后可能都会回到1顶点。

实测这样写也可以过：（969ms）

void lca(int u, int v) {
	if(dfn[u] > dfn[v]) swap(u,v); 
	while(dfn[v] > dfn[u]) {
		if(qiao[v]) ans--;
		qiao[v] = 0;
		v = fa[v];
	}
	while(u != v) {
		if(qiao[u]) ans--;
		qiao[u] = 0;
		u = fa[u];
	}
}

AC代码2：（缩点+lca）（2891ms）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Edge {
	int u,v;
	int ne;
} e[MAX<<1];
vector<int> vv[MAX];
int dep[MAX]; 
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点，is数组用来记录构造的那棵树上的每一个新顶点编号，是否还没被遍历过。 也就是用一个点去代表这个边双连通分量
int n,m,ans;
void init() {
	for(int i = 1; i<=n; i++) {
		dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;
		head[i] = -1;
		vv[i].clear();
	}
	tot = 0;
	clk = index = bcc = 0;
	ans = 0;
}
void add(int u,int v) {
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].ne = head[u];
	head[u] = tot;
}
void tarjan(int x,int rt) {
	dfn[x] = low[x] = ++clk;
	stk[++index] = x;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].v;
		if(v == rt) continue;
		if(dfn[v] == 0) {
			tarjan(v,x);
			low[x] = min(low[x],low[v]);
			if(low[v] > dfn[x]) {
				qiao[v] = 1;
				ans++;
			}
		} else low[x] = min(low[x],dfn[v]);
	}
	if(dfn[x] == low[x]) {
		bcc++;//理论上来说应该等于ans+1 
		while(1) {
			int tmp = stk[index];index--;
			col[tmp] = bcc;
			if(tmp == x) break;
		}
	}
}
void bfs() {
	queue<int> q;
	q.push(1);
	//init
	for(int i = 1; i<=n; i++) dep[i]=0,is[i]=0;
	is[1]=0;
	dep[1]=1;
	fa[1] = -1;//人为规定一个 
	while(!q.empty()) {
		int cur = q.front();q.pop();
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			int v = vv[cur][i];
			if(dep[v]) continue;
			dep[v] = dep[cur] + 1;
			fa[v] = cur;
			is[v]=1; 
			q.push(v); 
		}
	}
}
void lca(int u,int v) {
	if(dep[u] < dep[v]) swap(u,v);
	while(dep[u] > dep[v]) {
		if(is[u]) ans--,is[u]=0;
		u = fa[u];
	} 
	if(u == v) return;
	while(u != v) {
		if(is[u]) ans--,is[u]=0;
		if(is[v]) ans--,is[v]=0;
		u = fa[u];v = fa[v];
	}
}
int main() 
{
	int a,b,iCase=0;
	while(~scanf("%d%d",&n,&m)) {
		if(n == 0 && m == 0) break;
		init();
		for(int i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b); add(b,a);
		}
		tarjan(1,0);
		for(int u = 1; u<=n; u++) {
			for(int i = head[u]; ~i; i = e[i].ne) {
				int v = e[i].v;
				if(qiao[v] == 0) continue;
				vv[col[u]].pb(col[v]);
				vv[col[v]].pb(col[u]);
			}
		}
		bfs();
		int q;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%d%d",&a,&b);
			lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc这条路径。 
			printf("%d\n", ans);
		}
		printf("\n");
	}
	return 0 ;
}

AC代码3：（454ms）

因为对于无向图的tarjan算法有一个性质，就是你只要搜素进去，那肯定就把这一个bcc全都搜完，然后再进入另一个。

换种方向考虑，因为是搜索，所以对于查询的两个点u和v，肯定有个他俩的共同起点（祖先），而由于搜索的特性，所以dfn[u]一直减小（通过让u=fa[u]），当dfn[u]<dfn[v]的时候，此时的u要么是v，要么是u和v的最近公共祖先。

对于很多跑的飞快（400ms左右）的代码，多半是用并查集来写的（把qiao数组换成了并查集来看，差不多这样，然后改一下 tarjan函数的关键点部分 和 lca函数的部分），但是对于lca部分，也是暴力，那么为什么会快这么多呢？研究了半天，发现就是因为他在进入lca函数之前加了一句if(col[a] != col[b]) ，代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Edge {
	int u,v;
	int ne;
} e[MAX<<1];
vector<int> vv[MAX];
int dep[MAX]; 
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点，is数组用来记录构造的那棵树上的每一个新顶点编号，是否还没被遍历过。 
int n,m,ans;
void init() {
	for(int i = 1; i<=n; i++) {
		dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;
		head[i] = -1;
		vv[i].clear();
	}
	tot = 0;
	clk = index = bcc = 0;
	ans = 0;
}
void add(int u,int v) {
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].ne = head[u];
	head[u] = tot;
}
void tarjan(int x,int rt) {
	dfn[x] = low[x] = ++clk;
	stk[++index] = x;
	fa[x] = rt;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].v;
		if(v == rt) continue;
		if(dfn[v] == 0) {
			tarjan(v,x);
			low[x] = min(low[x],low[v]);
			if(low[v] > dfn[x]) {
				qiao[v] = 1;
				ans++;
			}
		} else low[x] = min(low[x],dfn[v]);
	}
	if(dfn[x] == low[x]) {
		bcc++;//理论上来说应该等于ans+1 
		while(1) {
			int tmp = stk[index];index--;
			col[tmp] = bcc;
			if(tmp == x) break;
		}
	}
}
void lca(int u, int v) {
	if(dfn[u] > dfn[v]) swap(u,v); 
	while(dfn[v] > dfn[u]) {
		if(qiao[v]) ans--;
		qiao[v] = 0;
		v = fa[v];
	}
	while(u != v) {
		if(qiao[u]) ans--;
		qiao[u] = 0;
		u = fa[u];
	}
}
int main() 
{
	int a,b,iCase=0;
	while(~scanf("%d%d",&n,&m)) {
		if(n == 0 && m == 0) break;
		init();
		for(int i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b); add(b,a);
		}
		tarjan(1,0);
		
		int q;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%d%d",&a,&b);
			if(col[a] != col[b]) lca(a,b);//每次暴力a的bcc 到 b的bcc这条路径。 
			printf("%d\n", ans);
		}
		printf("\n");
	}
	return 0 ;
}

思考：

对于AC代码1中的那个改进，我们拿到AC代码2的思路来行不行呢？

答案是不行的，因为你将图转化成了一棵树，然后用bfs生成的dep数组去做lca，（lca做法也是：先把u设置成dep大的，然后让u一直向上找,一直到dep[u] <= dep[v]则第一个循环结束，然后再只动v，一直到u==v则第二个循环结束）那么得到的当dep[u] <= dep[v]了之后，不能确保：此时的u要么等于v，要么是u和v的最近公共祖先，（想想普通的倍增做的lca的图呀，很容易找到反例）所以不能这样做，不然会出现v==1了，但是u还在下面，这样就死循环了，所以会TLE。

TLE代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Edge {
	int u,v;
	int ne;
} e[MAX<<1];
vector<int> vv[MAX];
int dep[MAX]; 
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点，is数组用来记录构造的那棵树上的每一个新顶点编号，是否还没被遍历过。 
int n,m,ans;
void init() {
	for(int i = 1; i<=n; i++) {
		dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;
		head[i] = -1;
		vv[i].clear();
	}
	tot = 0;
	clk = index = bcc = 0;
	ans = 0;
}
void add(int u,int v) {
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].ne = head[u];
	head[u] = tot;
}
void tarjan(int x,int rt) {
	dfn[x] = low[x] = ++clk;
	stk[++index] = x;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].v;
		if(v == rt) continue;
		if(dfn[v] == 0) {
			tarjan(v,x);
			low[x] = min(low[x],low[v]);
			if(low[v] > dfn[x]) {
				qiao[v] = 1;
				ans++;
			}
		} else low[x] = min(low[x],dfn[v]);
	}
	if(dfn[x] == low[x]) {
		bcc++;//理论上来说应该等于ans+1 
		while(1) {
			int tmp = stk[index];index--;
			col[tmp] = bcc;
			if(tmp == x) break;
		}
	}
}
void bfs() {
	queue<int> q;
	q.push(1);
	//init
	for(int i = 1; i<=n; i++) dep[i]=0,is[i]=0;
	is[1]=0;
	dep[1]=1;
	fa[1] = -1;//人为规定一个 
	while(!q.empty()) {
		int cur = q.front();q.pop();
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			int v = vv[cur][i];
			if(dep[v]) continue;
			dep[v] = dep[cur] + 1;
			fa[v] = cur;
			is[v]=1; 
			q.push(v); 
		}
	}
}
void lca(int u,int v) {
	if(dep[u] < dep[v]) swap(u,v);
	while(dep[u] > dep[v]) {
		if(is[u]) ans--,is[u]=0;
		u = fa[u];
	} 
	if(u == v) return;
	while(u != v) {
		if(is[v]) ans--,is[v]=0;
		v = fa[v];
	}
}
int main() 
{
	int a,b,iCase=0;
	while(~scanf("%d%d",&n,&m)) {
		if(n == 0 && m == 0) break;
		init();
		for(int i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b); add(b,a);
		}
		tarjan(1,0);
		for(int u = 1; u<=n; u++) {
			for(int i = head[u]; ~i; i = e[i].ne) {
				int v = e[i].v;
				if(qiao[v] == 0) continue;
				vv[col[u]].pb(col[v]);
				vv[col[v]].pb(col[u]);
			}
		}
		bfs();
		int q;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%d%d",&a,&b);
			if(col[a] != col[b]) lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc这条路径。 
			printf("%d\n", ans);
		}
		printf("\n");
	}
	return 0 ;
}