Description
在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。
但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。
Data Constraint
对于10%的数据有1≤N,M,P≤100；
对于40%的数据有1≤N,M,P≤2000；
对于100%的数据有1≤N,M,P≤200000。
Solution
这道题是一道显然的并查集的题。我们先将输入和询问的边连起来构成一个森林。这样就可以保证若两点相连，则表示他们之间原本是不相连的，直接输出No。那么对于那些可以构成环的输入和询问，显然会使两点x,y和他们的公共祖先z构成一个环。所以我们从x,y一直往上跳，每次将x,y所属的并查集并入z所属的并查集,并跳上x,y所属的并查集顶点在树中的父亲。时间复杂度O(
Code
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=5e5+7;
int i,j,k,l,t,n,m,ans,p;
int first[maxn*2],next[maxn*2],last[maxn*2],num,tot,x,y,o;
int a[maxn],b[maxn],deep[maxn],f[maxn],f1,f2,cnt[maxn];
int fa[maxn];
bool bz[maxn];
void add(int x,int y){
last[++num]=y,next[num]=first[x],first[x]=num;
}
int gf(int x){
if(fa[x]==x)return x;
fa[x]=gf(fa[x]);return fa[x];
}
void dfs(int x,int y){
int i;
deep[x]=deep[y]+1,f[x]=y;
rep(i,x){
if(last[i]!=y){
dfs(last[i],x);
}
}
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
fo(i,1,n)fa[i]=i;
fo(i,1,m){
scanf("%d%d",&k,&l);a[i]=k,b[i]=l;
x=gf(k),y=gf(l);
if(x!=y)fa[x]=y,add(k,l),add(l,k),bz[i]=1;
}
fo(i,1,p){
scanf("%d%d",&a[i+m],&b[i+m]);
x=gf(a[i+m]),y=gf(b[i+m]);
if(x!=y)fa[x]=y,add(a[i+m],b[i+m]),add(b[i+m],a[i+m]),bz[i+m]=1;
}
fo(i,1,n)if(!deep[i])dfs(i,0);
fo(i,1,n)cnt[i]=1,fa[i]=i;
fo(i,1,p+m){
if(!bz[i]){
x=gf(a[i]),y=gf(b[i]);
if(x==y){
if(i>m)printf("%d\n",cnt[x]);
continue;
}
while(x!=y){
gf(f[x]),gf(f[y]);
if(deep[x]>deep[y])x=fa[f[x]];else y=fa[f[y]];
}
o=x;
x=fa[a[i]],y=fa[b[i]];
while(x!=y){
if(deep[x]>deep[y])fa[x]=fa[o],cnt[o]+=cnt[x],x=fa[f[x]];
else fa[y]=fa[o],cnt[o]+=cnt[y],y=fa[f[y]];
}
if(i>m)printf("%d\n",cnt[o]);
}
else if(i>m)printf("No\n");
}
}