【题解】POJ3694

Link \text{Link} Link

题意

给定一张有 n n n 个点和 m m m 条边的无向连通图，有 q q q 次操作，每次往图中添加一条无向边，并询问添加后图中 桥 的数量。

思路

先用求出图中的边双并缩点，顺便求出一开始桥的数量，设 c x c_x cx​​ 表示点 x x x​ 所属的边双编号。

对于添加边 ( u , v ) (u,v) (u,v)：

1. c u = c v c_u=c_v cu​=cv​：添加后桥的数量不变。
2. c u ≠ c v c_u\ne c_v cu​​=cv​：在缩点后， c u ∼ c v c_u\sim c_v cu​∼cv​ 的路径上的边处在一个环内，都不是桥。求出 LCA ⁡ ( c u , c v ) \operatorname{LCA}(c_u,c_v) LCA(cu​,cv​)，从 c u c_u cu​ 一直走到 L C A LCA LCA，再从 c v c_v cv​​ 一直走到 L C A LCA LCA​，把经过的边标记为非桥边，统计有多少条边被新标记了，则将桥的总数减去被新标记的边的数量即可。

时间复杂度为 O ⁡ ( q n ) \operatorname{O}(qn) O(qn)​​​，因为数据范围较水可以过，但热爱 卡时 思考的我们可以进一步优化。很显然当一条边是非桥边后，如何添加边也不会使得其重新变为桥边，所以被标记后直接并入父节点所在的集合即可，这里直接用并查集维护，时间复杂度为 O ⁡ ( q log ⁡ n ) \operatorname{O}(q\log n) O(qlogn)。

Code \text{Code} Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;

int n, m, dcc, ans;

struct node1
{
	int cnt, Time;
	int head[MAXN], dfn[MAXN], low[MAXN], c[MAXN];
	bool bridge[MAXM << 1];
	
	struct edge
	{
		int to, nxt;
	}e[MAXM << 1];
	
	void init()
	{
		cnt = 1;
		Time = dcc = 0;
		memset(head, 0, sizeof(head));
		memset(dfn, 0, sizeof(dfn));
		memset(c, 0, sizeof(c));
		memset(bridge, false, sizeof(bridge));
	}
	
	void add(int u, int v)
	{
		e[++cnt] = edge{v, head[u]};
		head[u] = cnt;
	}
	
	void tarjan(int u, int in_edge) 
	{
		dfn[u] = low[u] = ++Time;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (!dfn[v])
			{
				tarjan(v, i);
				low[u] = min(low[u], low[v]);
				if (dfn[u] < low[v])
				{
					bridge[i] = bridge[i ^ 1] = true;
				}
			}
			else if (i != (in_edge ^ 1))
			{
				low[u] = min(low[u], dfn[v]);
			}
		}
	}
	
	void dfs(int u)
	{
		c[u] = dcc;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (c[v] || bridge[i])
			{
				continue;
			}
			dfs(v);
		}
	}
}old;

struct node2
{
	int cnt;
	int head[MAXN], fa[MAXN][18], dep[MAXN], f[MAXN];
	
	struct edge
	{
		int to, nxt;
	}e[MAXM << 1];
	
	void Init()
	{
		for (int i = 1; i <= dcc; i++)
		{
			f[i] = i;
		}
	}
	
	void init()
	{
		cnt = 0;
		memset(head, 0, sizeof(head));
		memset(dep, 0, sizeof(dep));
		Init();
	}
	
	void add(int u, int v)
	{
		e[++cnt] = edge{v, head[u]};
		head[u] = cnt;
	}
	
	void dfs(int u, int father)
	{
		fa[u][0] = father;
		dep[u] = dep[father] + 1;
		for (int i = 1; i <= 17; i++)
		{
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (!dep[v])
			{
				dfs(v, u);
			}
		}
	}
	
	int lca(int x, int y)
	{
		if (dep[x] < dep[y])
		{
			swap(x, y);
		}
		for (int i = 17; i >= 0; i--)
		{
			if (dep[fa[x][i]] >= dep[y])
			{
				x = fa[x][i];
			}
		}
		if (x == y)
		{
			return x;
		}
		for (int i = 17; i >= 0; i--)
		{
			if (fa[x][i] != fa[y][i])
			{
				x = fa[x][i], y = fa[y][i];
			}
		}
		return fa[x][0];
	}
	
	int find(int x)
	{
		if (x == f[x])
		{
			return x;
		}
		return f[x] = find(f[x]);
	}
	
	void work(int x, int y)
	{
		x = find(x);
		while (dep[x] > dep[y])
		{
			f[x] = fa[x][0];
			ans--;
			x = find(x);
		}
	}
}now;

int main()
{
	int t = 0;
	while (scanf("%d%d", &n, &m), n + m)
	{
		printf("Case %d:\n", ++t);
		dcc = 0;
		old.init();
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			old.add(u, v);
			old.add(v, u);
		}
		for (int i = 1; i <= n; i++)
		{
			if (!old.dfn[i])
			{
				old.tarjan(i, 0);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			if (!old.c[i])
			{
				dcc++;
				old.dfs(i);
			}
		}
		now.init();
		for (int u = 1; u <= n; u++)
		{
			for (int i = old.head[u]; i; i = old.e[i].nxt)
			{
				int v = old.e[i].to;
				if (old.c[u] != old.c[v])
				{
					now.add(old.c[u], old.c[v]);
					now.add(old.c[v], old.c[u]);
				}
			}
		}
		now.dfs(1, 0);
		int q;
		scanf("%d", &q);
		ans = dcc - 1;
		while (q--)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			a = old.c[a], b = old.c[b];
			int c = now.lca(a, b);
			now.work(a, c);
			now.work(b, c);
			printf("%d\n", ans);
		}
		putchar('\n');
	}
	return 0;
}