连通块中 点的数量

using namespace std;
const int N = 1e5 + 10;
int p[N], len[N];
int find(int x)//返回x的祖宗节点 + 路径压缩
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin >> n >>m;
    for(int i = 1; i <= n; i ++){
        p[i] = i;
        len[i] = 1;
    }
    while(m --)
    {
        char op[4];
        int a, b;
        cin >>op;
        if(op[0] =='C')
        {
            cin >>a >>b;
            if(find(a)==find(b))continue;
            len[find(b)] += len[find(a)];
            p[find(a)] = find(b);
            
        }
        else if(op[1]=='1'){
            cin >>a >>b;
            if(find(a) != find(b))cout <<"No"<<endl;
            else cout << "Yes"<<endl;
        }
        else {
            cin >> a;
            cout << len[find(a)]<<endl;
        }
    }
}
全部评论

相关推荐

无敌虾孝子:喜欢爸爸还是喜欢妈妈
点赞 评论 收藏
分享
手撕没做出来是不是一定挂
Chrispp3:不会,写出来也不一定过
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务