「bzoj4998」星球联盟 - 并查集+LCA

题目大意

    在遥远的S星系中一共有$N$个星球，编号为$1\ldots N$。其中的一些星球决定组成联盟，以方便相互间的交流。
    但是，组成联盟的首要条件就是交通条件。初始时，在这$N$个星球间有$M$条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
    为了壮大联盟的队伍，这些星球将建设$P$条新的太空隧道。这$P$条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。

---

题目分析

考虑对原图缩点，每次缩点后原图的规模必定会减小。
每个点只可能被缩点一次，而缩点后块的大小即为每次询问的答案。

考虑使用并查集维护块，以深度最小的结点作为并查集的根。
那么每一次我们在缩点后的树上进行爬树爬到$lca$即可找到需要缩块的所有结点。

考虑，原图并不连通，且动态加边，如何维护出这样的一棵树呢？

我们可以离线处理，先离线将所有连通两个集合的DFS树边加入边集，对于其他的返祖边不予处理。
若原图仍不连通，强行使得其他的结点连向$1$。（这里的$1$可以换成其他的任何数，只要保证能连通，正确性在于这两个集合永远不会被合并掉，因此只要连起来就是可行的）

这样连通后预处理出树，每次暴力爬树并缩块即可。

本题与 「poj3694」网络 颇为相似。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=200005;

int n,m,q,prt[maxn],Ans[maxn],Depth[maxn],father[maxn],Size[maxn],top=0,cnt=0;
struct Point {
	int x,y,opt;
	Point(int _x=0,int _y=0):x(_x),y(_y),opt(0) {}
} a[maxn],b[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
	edges[x].push_back(y);
	edges[y].push_back(x);
}

int Get_Father(int x) {
	if(father[x]==x)return x;
	return father[x]=Get_Father(father[x]);
}

void Dfs(int Now,int fa) {
	prt[Now]=fa;
	Depth[Now]=Depth[fa]+1;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(Next==fa)continue;
		Dfs(Next,Now);
	}
}

int LCA(int x,int y) {
	x=Get_Father(x);
	y=Get_Father(y);
	if(Depth[x]<Depth[y])swap(x,y);
	while(Get_Father(x)!=Get_Father(y)) {
		int Nowx=Get_Father(x),Nowy=Get_Father(prt[Nowx]);
		if(Nowx!=Nowy) {
			Size[Nowy]+=Size[Nowx];
			father[Nowx]=Nowy;
		}
		x=Nowy;
		if(Depth[x]<Depth[y])swap(x,y);
	}
	return Get_Father(x);
}

int main() {
	n=Get_Int();
	m=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++)father[i]=i;
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		int fx=Get_Father(x),fy=Get_Father(y);
		if(fx!=fy) {
			father[fy]=fx;
			AddEdge(x,y);
		} else b[++cnt]=Point(x,y);
	}
	for(int i=1; i<=q; i++) {
		int x=Get_Int(),y=Get_Int();
		int fx=Get_Father(x),fy=Get_Father(y);
		if(fx!=fy) {
			father[fy]=fx;
			AddEdge(x,y);
			a[i].opt=1;
		}
		a[i].x=x;
		a[i].y=y;
	}
	for(int i=1; i<=n; i++) {
		int x=Get_Father(1),y=Get_Father(i);
		if(x!=y) {
			father[y]=x;
			AddEdge(1,i);
		}
	}
	Dfs(1,0);
	for(int i=1; i<=n; i++)father[i]=i,Size[i]=1;
	for(int i=1; i<=cnt; i++)LCA(b[i].x,b[i].y);
	for(int i=1; i<=q; i++)
		if(a[i].opt!=1) {
			int lca=LCA(a[i].x,a[i].y);
			Ans[i]=Size[lca];
		}
	for(int i=1; i<=q; i++)
		if(a[i].opt==1)puts("No");
		else printf("%d\n",Ans[i]);
	return 0;