GMOJ S3875 【星球联盟】

Description

给你 $n$ 个点， $m$ 条边，给出 $p$ 个询问，每个询问给出一条边，先连这条边，然后判断两个点是否处在同一个环内，是的话就输出环的大小，否则输出 No 。

$$1 \leq n;m;p \leq 2 \times 10^5$$

Solution

考虑先把这 $(m + p)$ 条边读进来，然后离线来做。

对于一条边，如果连它不会成环，那么我们就连它。

那么最后我们会得到一棵树 $T$ 。

对于一条边 $(u, v) \in T$ ，连完之后会让 $u$ 到 $v$ 的简单路径上的所有点处于一个环中。

不断这样做的过程和 并查集 有异曲同工之妙，考虑使用 并查集 来算答案。

我们将深度深的点的祖宗设为深度浅的点，这样祖宗就不断往上靠了。

对于要合并 $u$ 到 $v$ 的简单路径上的点的祖宗，可以选择从 $u$ 一直更新到 $lca(u, v)$ ，从 $v$ 到 $lca(u, v)$ 。

但这样复杂度是 $O(n ^ 2)$ 的。

为了保证复杂度，我们可以每次跳到一个点的祖宗，更新完以后跳到它的父亲。

因为我们前面深度深的点的祖宗设为深度浅的点，因此我们是不断往上跳的。

为了检测有没有跳过，我们还要判断当前跳到的点与 $lca(u, v)$ 的最近公共祖先是否是 $lca(u, v)$ 。

然后我们就得到了一个时间复杂度为 $O(n \log n)$ 的做法。

Code

#include <cstdio>
#include <cstdlib>
#define maxN 200010
#define maxM 500010
struct node{ int x, y, c, g, link; } a[maxM], b[maxM];
int f[maxN][21], size[maxN], dep[maxN], fa1[maxN], fa2[maxN], h[maxN];
int len = 0;
int read ()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y, int c)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].c = c;
	b[len].g = h[x];
	h[x] = len;
}
void dfs (int x)
{
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!dep[y])
		{
			dep[y] = dep[x] + 1;
			f[y][0] = x;
			dfs(y);
		}
	}
}
int find1 (int x)
{
	if(x == fa1[x])
	{
		return x;
	}
	else
	{
		return fa1[x] = find1(fa1[x]);
	}
}
int find2 (int x)
{
	if(x == fa2[x])
	{
		return x;
	}
	else
	{
		return fa2[x] = find2(fa2[x]);
	}
}
void hb2 (int x, int y)
{
	int tx = find2(x);
	int ty = find2(y);
	if(tx != ty)
	{
		if(dep[tx] < dep[ty])
		{
			int t = tx;
			tx = ty;
			ty = t;
		}
		size[ty] += size[tx];
		size[tx] = 0;
		fa2[tx] = ty;
	}
}
int lca (int x, int y)
{
	if(!x || !y)
	{
		return 0;
	}
	if(dep[x] < dep[y])
	{
		int t = x;
		x = y;
		y = t;
	}
	for(int i = 20;i >= 0; i--)
	{
		if(f[x][i] && dep[f[x][i]] >= dep[y])
		{
			x = f[x][i];
		}
	}
	if(x == y)
	{
		return x;
	}
	for(int i = 20;i >= 0; i--)
	{
		if(f[x][i] && f[y][i] && f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
void color (int x, int y)
{
	int now = x, LCA = lca(x, y);
	while(true)
	{
		int nNOW = find2(now);
		hb2(now, LCA);
		now = nNOW;
		now = f[now][0];
		if(lca(now, LCA) != LCA)
		{
			break;
		}
	}
	now = y;
	while(true)
	{
		int nNOW = find2(now);
		hb2(now, LCA);
		now = nNOW;
		now = f[now][0];
		if(lca(now, LCA) != LCA)
		{
			break;
		}
	}
}
int main ()
{
	int n = 0, m = 0, q = 0;
	n = read();
	m = read();
	q = read();
	for(int i = 1;i <= m + q; i++)
	{
		a[i].x = read();
		a[i].y = read();
	}
	for(int i = 1;i <= n; i++)
	{
		fa1[i] = i;
	}
	for(int i = 1;i <= m + q; i++)
	{
		int x = a[i].x, y = a[i].y;
		int tx = find1(x);
		int ty = find1(y);
		if(tx != ty)
		{
			a[i].link = 1;
			if(i <= m)
			{ 
				ins(x, y, 0);
				ins(y, x, 0);
			}
			else
			{
				ins(x, y, i + 1);
				ins(y, x, i + 1); 
			}
			fa1[tx] = ty;
		}
	}
	for(int i = 1;i <= n; i++)
	{
		if(!dep[i])
		{
			dep[i] = 1;
			dfs(i);
		}
	}
	for(int j = 1;j <= 20; j++)
	{
		for(int i = 1;i <= n; i++)
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	for(int i = 1;i <= n; i++)
	{
		fa2[i] = i;
		size[i] = 1;
	}
	for(int i = 1;i <= m + q; i++)
	{
		if(!a[i].link)
		{
			int x = a[i].x, y = a[i].y;
			if(dep[x] < dep[y])
			{
				int t = x;
				x = y;
				y = t;
			}
			color(x, y);
			if(i > m)
			{
				printf("%d\n", size[find2(x)]);
			}
		}
		else if(i > m)
		{
			printf("No\n");
		}
	}
	return 0;
}