连通块中 点的数量

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;
        }
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:15
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务