求连通块中点数

本文主要是介绍求连通块中点数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

可以将连通块看成集合，合并连通块可以看成将集合合并，但是要注意存储连通块中的点数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int p[N], cnt[N];
int find(int x) //查询加路径压缩
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        cnt[i] = 1;
    }
    while (m -- )
    {
        string op;
        int a, b;
        cin>>op;
        if(op == "C")
        {
            cin>>a>>b;
            a = find(a), b = find(b);
            if(a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if(op == "Q1")
        {
            cin>>a>>b;
            if(find(a) == find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<cnt[find(a)]<<endl;
        }
    }
    return 0;
}

这篇关于求连通块中点数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！