POJ 3694 network 无向图求桥 手写栈版tarjan
这题以前做过
大意就是给出一个无向图，然后每次询问加一条边，然后输出当前图中剩余的桥的个数
大概做法就是先tarjan把桥都弄出来，然后每次加边就裸求LCA。
不过很蛋疼的事情就是在HDU上会爆栈，这很贱，所以有必要弄个手写栈版得tarjan
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define MAXN 111111#define MAXM 555555#define INF 1000000011#define lch(x) x<<1#define rch(x) x<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define eps 1e-7using namespace std;struct Edge{ int v, next;}edge[MAXM];int head[MAXN], e, n, m;int dfn[MAXN], low[MAXN], fa[MAXN];int index, tmpdfn, vis[MAXN];int cnt, bridge[MAXN];int st[MAXN];void init(){ e = index = cnt = 0; memset(vis, 0, sizeof(vis)); memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(bridge, 0, sizeof(bridge)); memset(head, -1, sizeof(head)); for(int i = 1; i <= n; i++) fa[i] = i;}void add(int u, int v){ edge[e].v = v; edge[e].next = head[u]; head[u] = e++;}void tarjan(){ int top = 0; st[++top] = 1; while(top) { int u = st[top]; if(!vis[u]) { dfn[u] = low[u] = ++index; vis[u] = 1; } int i; for(i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(!vis[v]) { fa[v] = u; break; } else if(vis[v] == 1 && v != fa[u]) low[u] = min(low[u], dfn[v]); } if(i == -1 && top > 1) { low[st[top - 1]] = min(low[u], low[st[top - 1]]); if(low[u] > dfn[st[top - 1]]) { bridge[u] = 1; cnt++; } } if(i == -1) { vis[u] = 2; top--; } else st[++top] = edge[i].v; }}void LCA(int u, int v){ while(dfn[u] > dfn[v]) { if(bridge[u]) cnt--, bridge[u] = 0; u = fa[u]; } while(dfn[v] > dfn[u]) { if(bridge[v]) cnt--, bridge[v] = 0; v = fa[v]; } while(u != v) { if(bridge[u]) cnt--, bridge[u] = 0; u = fa[u]; if(bridge[v]) cnt--, bridge[v] = 0; v = fa[v]; }}void gao(){ int q; scanf("%d", &q); while(q--) { int x, y; scanf("%d%d", &x, &y); LCA(x, y); printf("%d\n", cnt); } printf("\n");}int main(){ int cas = 0; while(scanf("%d%d", &n, &m) != EOF) { if(!n && !m) break; init(); int x, y; while(m--) { scanf("%d%d", &x, &y); add(x, y); add(y, x); } tarjan(); printf("Case %d:\n", ++cas); gao(); } return 0;}