题意
就是给出一个图，然后不断地给它加边，问有多少条桥
思路
首先这题其实和poj1679有点像 为什么这么说呢， 因为只要先求一次桥，然后就把双连通分量缩点，然后每一次连的边就可以相当于是求LCA，然后暴力LCA时经过的桥就不是桥了。然后看了网上一些题解发现连缩点都不用，可以直接用原来的点来做LCA。 因为反向边必然不是桥，所以只有树边会是桥。所以沿着树边做LCA的过程其实就可以把缩点略过了←_← 然后标记桥的时候可以直接标记点，然后从这个点连到父亲的点就是桥，然后做LCA的时候也很容易就求出来了。 最后交了很多次都是TLE，最后发现是数组没开够……那么为什么数组没开够会TLE，不应该是RE吗……
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 100010,
MAXM = 400010;
struct Edge {
int u, v, ne;
} e[MAXM];
int head[MAXN];
int n, m;
int m_cnt;
int pre[MAXN], low[MAXN], dfs_clock;
int fa[MAXN], dep[MAXN], bridge_cnt;
bool is_bridge[MAXM];
void dfs(int u) {
low[u] = pre[u] = ++dfs_clock;
dep[u] = dep[fa[u]] + 1;
for(int i = head[u]; ~i; i = e[i].ne) {
int v = e[i].v;
if(!pre[v]) {
fa[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
if(low[v] > pre[u]) {
is_bridge[v] = 1;
bridge_cnt++;
}
} else {
if(pre[v] < pre[u] && v != fa[u]) {
low[u] = min(low[u], pre[v]);
}
}
}
}
void find_bcc(int n) {
memset(pre, 0, sizeof pre);
memset(is_bridge, 0, sizeof is_bridge);
dfs_clock = 0;
dfs(1);
}
void AddEdge(int u, int v) {
e[m_cnt].u = u;
e[m_cnt].v = v;
e[m_cnt].ne = head[u];
head[u] = m_cnt++;
}
void init() {
memset(head, -1, sizeof head);
m_cnt = 0;
}
void LCA(int u, int v) {
while (dep[u] > dep[v]) {
if(is_bridge[u]) {
bridge_cnt--;
is_bridge[u] = 0;
}
u = fa[u];
}
while (dep[v] > dep[u]) {
if(is_bridge[v]) {
bridge_cnt--;
is_bridge[v] = 0;
}
v = fa[v];
}
while(u != v) {
if(is_bridge[u]) {
bridge_cnt--;
is_bridge[u] = 0;
}
u = fa[u];
if(is_bridge[v]) {
bridge_cnt--;
is_bridge[v] = 0;
}
v = fa[v];
}
}
int main(void) {
int Case = 0;
while (~scanf("%d%d", &n, &m) && n != 0 && m != 0) {
init();
for(int i = 0; i < m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v);
AddEdge(v, u);
}
find_bcc(n);
printf("Case %d:\n", ++Case);
int q;
scanf("%d", &q);
for(int i = 0; i < q; ++i) {
int u, v;
scanf("%d%d", &u, &v);
LCA(u, v);
printf("%d\n", bridge_cnt);
}
printf("\n");
}
return 0;
}
