4998: 星球联盟 LCT+并查集

星球联盟 LCT+并查集"/>

4998: 星球联盟 LCT+并查集

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

题解：

这道题也很强啊，像我这样的蒟蒻就只会判No……思路大概是这样的： f[0][x] f [ 0 ] [ x ] $f[0][x]$表示 x x $x$所在的连通块是什么（就是并查集的东西），f[1][x]" role="presentation" style="position: relative;">f[1][x]f[1][x]$f[1][x]$表示 x x <script type="math/tex" id="MathJax-Element-257">x</script>实际上代表的是哪一个点，然后对于每次连边，若不在同一个连通块，那显然输出No就可以了，然后在LCT上连边；否则就把两点间的点都缩为一个点，具体的方法是暴力搞……但是由于每个点只会被缩一次，所以时间复杂度是有保证的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=200010;
const int inf=2147483647;
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
int n,m,p;
int f[2][Maxn];//f[0]为并查集关系 f[1]为这个点实际上是什么点 
int findfa(int o,int x){return(f[o][x]=((f[o][x]==x)?x:findfa(o,f[o][x])));}
int fa[Maxn],son[Maxn][2],rev[Maxn],size[Maxn];
void down(int x)
{int lc=son[x][0],rc=son[x][1];if(rev[x]){swap(son[x][0],son[x][1]);if(lc)rev[lc]^=1;if(rc)rev[rc]^=1;rev[x]=0;}
}
bool is(int x){return(son[findfa(1,fa[x])][0]!=x&&son[findfa(1,fa[x])][1]!=x);}
void rotate(int x)
{int y=findfa(1,fa[x]),z=findfa(1,fa[y]),w=(son[y][0]==x);son[y][w^1]=son[x][w];if(son[x][w])fa[son[x][w]]=y;if(!is(y))son[z][son[z][1]==y]=x;fa[x]=z;son[x][w]=y;fa[y]=x;
}
int sta[Maxn],top;
void update(int x)
{top=0;while(x)sta[++top]=x,x=findfa(1,fa[x]);while(top)down(sta[top--]);
}
void splay(int x)
{update(x);while(!is(x)){int y=findfa(1,fa[x]),z=findfa(1,fa[y]);if(!is(y))rotate(((son[z][1]==y)==(son[y][1]==x))?y:x);rotate(x);}
}
void access(int x)
{int last=0;while(x){splay(x);son[x][1]=last;last=x;x=findfa(1,fa[x]);}
}
void make_root(int x){access(x),splay(x),rev[x]^=1;}
void split(int x,int y){make_root(x),access(y),splay(y);}
void link(int x,int y){make_root(x),fa[x]=y;}
void dfs(int x,int rt)
{if(!x)return;if(x!=rt)f[1][x]=rt,size[rt]+=size[x];dfs(son[x][0],rt),dfs(son[x][1],rt);
}
void Link(int x,int y,int type)
{x=findfa(1,x),y=findfa(1,y);int fx=findfa(0,x),fy=findfa(0,y);if(fx!=fy){if(type)puts("No");f[0][fx]=fy;link(x,y);return;}split(x,y);dfs(y,y);son[y][0]=son[y][1]=0;if(type)printf("%d\n",size[y]);
}
int main()
{n=read(),m=read(),p=read();for(int i=1;i<=n;i++)f[0][i]=f[1][i]=i,size[i]=1;for(int i=1;i<=m;i++)Link(read(),read(),0);for(int i=1;i<=p;i++)Link(read(),read(),1);
}