fg
在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。
但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。
对于100%的数据有1≤N,M,P≤200000。
hdj
顺次连接给定的边，判断哪些是树边。
（树边，也即两端点所在的连通块不同）
知道哪些是树边之后，很容易知道什么询问输出No。
然后，对于其他边(u,v)，会使得u到v这条树上路径的所有点归于同一个连通块。
所以利用并查集可以快速求出连通块的大小。
code
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
const char* fin="aP3.in";
const char* fout="aP3.out";
const int inf=0x7fffffff;
const int maxn=500007,maxq=maxn,maxm=maxn*2;
int n,m,Q,i,j,k;
int dad[maxn],num[maxn],fa[maxn],de[maxn];
int fi[maxn],la[maxm],ne[maxm],tot;
bool bz[maxn];
struct query{
int x,y,id;
}q[maxn];
int getdad(int x){
if (!dad[x]) return x;
dad[x]=getdad(dad[x]);
return dad[x];
}
void add_line(int a,int b){
tot++;
ne[tot]=fi[a];
la[tot]=b;
fi[a]=tot;
}
void dfs(int v,int from){
int i,j,k;
de[v]=de[from]+1;
for (k=fi[v];k;k=ne[k])
if (la[k]!=from){
fa[la[k]]=v;
dfs(la[k],v);
}
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
for (i=1;i<=m+Q;i++){
scanf("%d%d",&q[i].x,&q[i].y);
q[i].id=i;
j=getdad(q[i].x);
k=getdad(q[i].y);
if (j!=k){
dad[j]=k;
add_line(q[i].x,q[i].y);
add_line(q[i].y,q[i].x);
}
}
for (i=1;i<=n;i++){
dad[i]=0;
num[i]=1;
}
for (i=1;i<=n;i++) if (!de[i]) dfs(i,0);
for (i=1;i<=m+Q;i++){
if (q[i].x==fa[q[i].y] || q[i].y==fa[q[i].x]){
if (fa[q[i].y]==q[i].x) swap(q[i].x,q[i].y);
if (!bz[q[i].x]){
bz[q[i].x]=true;
if (i>m) printf("No\n");
}else{
j=getdad(q[i].x);
k=getdad(q[i].y);
if (j!=k){
dad[j]=k;
num[k]+=num[j];
}
if (i>m){
int ans=num[getdad(q[i].x)];
printf("%d\n",ans);
}
}
}else{
j=getdad(q[i].x);
k=getdad(q[i].y);
int l=0;
while (j!=k){
if (l==10000){
printf("");
}
if (de[j]>de[k]){
dad[j]=fa[j];
num[getdad(fa[j])]+=num[j];
j=getdad(fa[j]);
}else{
dad[k]=fa[k];
num[getdad(fa[k])]+=num[k];
k=getdad(fa[k]);
}
l++;
}
if (i>m) printf("%d\n",num[j]);
}
}
return 0;
}=o=
生成树对连通分量问题有关系。