连通块中 点的数量

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

相关推荐

04-13 18:10
门头沟学院 Java
想熬夜的小飞象在秋招:被腾讯挂了后爸妈以为我失联了
点赞 评论 收藏
分享
SHC2:关键问题是你这三段实习是三个不同的岗位…你这样子秋招就是只有一段实习的本科生..
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务