AcWing 837. 连通块中点的数量并查集

2021-01-08 03:30

阅读：786

标签：merge char c++ ret begin problem 指令 content rip

地址 https://www.acwing.com/problem/content/description/839/

给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。

现在要进行m个操作，操作共有三种：

“C a b”，在点a和点b之间连一条边，a和b可能相等；
“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
“Q2 a”，询问点a所在连通块中点的数量；
输入格式
第一行输入整数n和m。

接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。

输出格式
对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。

对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3

算法1
(暴力枚举) O(n2)O(n2)
起始每次遇到并查集的题目，总会下意识的先去想想哈希。
但是哈希的合并那就逊色多了。不过这次也AC了。
计算相同集合里的个数要注意了，尽量在合并的时候注意次序，
序号小的统计记录不重复的记录下之后的所有大序号元素的个数。

序号大的元素记录里不要统计小序号元素个数，避免重复。

C++ 代码

#include 
#include 
#include set>
using namespace std;


/*
//并查集模板
void init(int n)
{
    for(int i=1;i*/

int n, m;

setint> ss[100010];

int cnt[100010];

int main()
{
    cin >> n >> m;

    for (int i = 1; i ) {
        ss[i].insert(i);
        cnt[i] = 1;
    }

    for (int i = 0; i ) {
        char op[10];
        cin >> op;
        if (op[0] == ‘C‘) {
            int a, b;
            cin >> a >> b;

            while (a != *ss[a].begin()) {
                a = *ss[a].begin();
            }
            while (b != *ss[b].begin()) {
                b = *ss[b].begin();
            }

            if(a !=b){
                if(a  b){
                    cnt[a] += cnt[b];
                    ss[b].insert(a);
                }
                else{
                    cnt[b] += cnt[a];
                    ss[a].insert(b);
                }
            }
        }
        else if (op[0] == ‘Q‘&& op[1] == ‘1‘) {
            int a; int b;
            cin >> a >> b;

            while (a != *ss[a].begin()) {
                a = *ss[a].begin();
            }
            while (b != *ss[b].begin()) {
                b = *ss[b].begin();
            }

            if (a == b) cout "Yes"  endl;
            else cout "No"  endl;

        }
        else if (op[0] == ‘Q‘&& op[1] == ‘2‘) {
            int a;
            cin >> a;

            while (a != *ss[a].begin()) {
                a = *ss[a].begin();
            }
            cout  endl;
        }
    }
}



作者：itdef
链接：https://www.acwing.com/solution/content/14781/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法2

正规并查集做法

同样的相同集合元素个数的记录也是要注意

序号小的统计记录不重复的记录下之后的所有大序号元素的个数。

序号大的元素记录里不要统计小序号元素个数，避免重复。

C++ 代码

#include using namespace std;

const int N = 100010;

int n,m;
int p[N],siz[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 ){
        p[i] = i;
        siz[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;
                siz[b] += siz[a];
            }
        }else if( op == "Q1"){
            cin >> a>> b;
            if(find(a) == find(b)) cout "Yes"  endl;
            else cout "No" endl;
        }else{
            cin >> a;
            cout  endl;
        }
    }



    return 0;
}



作者：itdef
链接：https://www.acwing.com/solution/content/14781/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include #include #include using namespace std;

/*//并查集模板void init(int n){ for(int i=1;i给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
“C a b”，在点a和点b之间连一条边，a和b可能相等；“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；“Q2 a”，询问点a所在连通块中点的数量；输入格式第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。
输出格式对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。
对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
数据范围1≤n,m≤105输入样例：5 5C 1 2Q1 1 2Q2 1C 2 5Q2 5输出样例：Yes23*/
int n, m;
set ss[100010];
int cnt[100010];
int main(){ cin >> n >> m;
for (int i = 1; i for (int i = 0; i > op; if (op[0] == ‘C‘) { int a, b; cin >> a >> b;
while (a != *ss[a].begin()) { a = *ss[a].begin(); } while (b != *ss[b].begin()) { b = *ss[b].begin(); }
if(a !=b){ if(a > a >> b;
while (a != *ss[a].begin()) { a = *ss[a].begin(); } while (b != *ss[b].begin()) { b = *ss[b].begin(); }
if (a == b) cout } else if (op[0] == ‘Q‘&& op[1] == ‘2‘) { int a; cin >> a;
while (a != *ss[a].begin()) { a = *ss[a].begin(); } cout

作者：itdef链接：https://www.acwing.com/solution/content/14781/来源：AcWing著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

AcWing 837. 连通块中点的数量并查集

标签：merge char c++ ret begin problem 指令 content rip

原文地址：https://www.cnblogs.com/itdef/p/13130223.html

上一篇：C# 如何在winform窗体自定义一个扁平化控件(转)

下一篇：C# 获取本地计算机IP地址

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 837. 连通块中点的数量并查集
文章链接：http://soscw.com/essay/40847.html

亲，登录后才可以留言！

AcWing 837. 连通块中点的数量并查集

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 837. 连通块中点的数量 并查集

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 837. 连通块中点的数量并查集