洛谷 1196 SSL 1225 银河英雄传说

题目

求战舰间有多少个战舰。

---

分析

并查集
fro表示到队头有多少个船舰。

---

代码

#include <cstdio>
#include <cctype>
using namespace std;
int t,f[30001],beh[30001],fro[30001],x,y; char k;
int getf(int u){
    if (f[u]==u) return u;
    int fu=getf(f[u]);
    fro[u]+=fro[f[u]];//回溯时也要更新
    return f[u]=fu;
}
int in(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
} 
int abs(int x){return (x>0)?x:-x;}
int main(){
    for (int i=1;i<=30000;i++) beh[i]=1,f[i]=i; t=in();
    while (t--){
        while (!isalpha(k)) k=getchar();
        x=in(); y=in();
        int fa=getf(x),fb=getf(y);
        if (k=='M'){
            f[fa]=fb;
            fro[fa]=beh[fb];
            beh[fb]+=beh[fa];
        }
        else if (fa!=fb) puts("-1");
        else printf("%d\n",abs(fro[x]-fro[y])-1);
        k=getchar();
    }
    return 0;
}