【題解】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;
}