poj3694

求双连通分量，利用并查集缩点，形成一棵树，树边肯定都是桥，然后每对点x,y,找原图中x,y点对应的新图中的点，如果不是一个点，则向上找它们的LCA,因为它们之间连了一条边，所以这些点到它们的LCA之间的边都不是割边了，找LCA时，先将两点上升到同一层次，然后一起再向上找父亲节点，其间遇到桥就把桥的标记删除，并且答案减1。

这个题比上一个好玩多了。

#include <iostream>

using namespace  std;

const int MAXN = 100005;

struct node {
	int to, next;
} edge[MAXN * 4];

int head[MAXN], dfn[MAXN], low[MAXN], pre[MAXN], vis[MAXN];
int n, m, timee, cnt, cut;
bool bi[MAXN];

void init() {
	memset(vis, 0, sizeof(vis));
	memset(head, -1, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	for (int i = 0; i <= n; pre[i] = i, i++) ;
	memset(bi, 0, sizeof(bi));
	cnt = 0;
	cut = 0;
	timee = 1;
}

void addedge(int u, int v) {
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
	cnt++;
}

void dfs(int u, int fa) {
	dfn[u] = timee;
	low[u] = timee;
	timee++;
	vis[u] = 1;
	for (int i = head[u]; i != -1; i = edge[i].next) {
		int v = edge[i].to;
		if (!vis[v]) {
			dfs(v, u);
			pre[v] = u;   //记录父节点
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) { //如果子节点的low值大于父节点的时间戳这就是桥
				cut++;
				bi[v] = true;
			}
		}
		else if (vis[v] == 1 && v != fa) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	vis[u] = 2;
}

int judge(int u, int v) {
	int cnt1 = 0;
	while (dfn[u] > dfn[v]) {
		if (bi[u]) {
			cnt1++;
			bi[u] = false;
		}
		u = pre[u];
	}
	while (dfn[u] < dfn[v]) {
		if (bi[v]) {
			cnt1++;
			bi[v] = false;
		}
		v = pre[v];
	}
	while (u != v) {
		if (bi[u]) {
			bi[u] = false;
			cnt1++;
		}
		if (bi[v]) {
			bi[v] = false;
			cnt1++;
		}
		u = pre[u];
		v = pre[v];
	}
	return cnt1;
}

int main() {
	int u, v, q, in = 0;
	while (scanf("%d%d", &n, &m), n + m) {
		if (in) {
			puts("");
		}
		in++;
		init();
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &u, &v);
			u--;
			v--;
			addedge(u, v);
			addedge(v, u);
		}
		dfs(0, 0);
		scanf("%d", &q);
		printf("Case %d:\n", in);
		for (int i = 0; i < q; i++) {
			scanf("%d%d", &u, &v);
			u--;
			v--;
			cut -= judge(u, v);
			printf("%d\n", cut);
		}
	}
	return 0;
}

poj3694,布布扣,bubuko.com

poj3694

原文：http://blog.csdn.net/zhengnanlee/article/details/22646327