题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 30010;
int p[N],siz[N],dist[N];
string op;
int a,b;

int find(int x)
{
if(x != p[x])
{
int t = find(p[x]);
dist[x] += dist[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
int t;
cin>>t;

for(int i = 1;i < N ;i++)p[i] = i,siz[i] = 1;

while(t--)
{
    cin>>op; 
    scanf("%d%d",&a,&b);
    int pa = find(a),pb = find(b);
    if(op[0] == 'M')
    {
        if(find(a) == find(b))continue;
        p[pa] = pb;
        dist[pa] = siz[pb];
        siz[pb] += siz[pa];
    }
    else{
        if(pa == pb)
        {
            cout<<max(0,abs(dist[b]-dist[a])-1)<<endl;
        }
        else cout<<-1<<endl;
    }
}
return 0;

}

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla