【NOIP2014八校联考第4场第2试10.20】星球联盟(alliance)

联考第4场第2试10.20】星球联盟(alliance)"/>

【NOIP2014八校联考第4场第2试10.20】星球联盟(alliance)

Description

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

Solution

一开始把询问的边和初始的边搞出一棵树，然后你一个个的合并就很容易了，把信息全部放到父亲那里就好了。

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("fan.in","r",stdin);
//  freopen("fan.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");}
}