luogu 1196 银河英雄传说 带权并查集

带权并查集,其实有点像许多队列问情况的小学奥数

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int N=;
inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
int fa[N],cnt[N],dfn[N],n,m,x,y,xx,yy;char s;
//dfn代表i和所在队列队头的距离
inline int aabs(int x){return x>?x:-x;}
inline int find(int x){
if(fa[x]==x) return x;
int ff=find(fa[x]);dfn[x]+=dfn[fa[x]];
fa[x]=ff;return ff;}
int main(){
m=read();n=;rep(i,,n) fa[i]=i,dfn[i]=,cnt[i]=;
while(m--){
cin>>s;x=read();y=read();
xx=find(x),yy=find(y);
if(s=='M')
fa[xx]=yy,dfn[xx]+=cnt[yy],cnt[yy]+=cnt[xx],cnt[xx]=;
else if(s=='C')
if(xx!=yy) printf("-1\n");
else printf("%d\n",aabs(dfn[x]-dfn[y])-);
}return ;
}
上一篇:爬虫之Scrapy详解


下一篇:Symfony2模版引擎使用说明手册