AcWing 837. 连通块中点的数量    原题链接    简单

作者： 作者的头像   小纸条o--o ,  2019-06-04 17:20:25 ,  所有人可见 ,  阅读 1745

1


题目描述

blablabla

样例

blablabla

blablabla

时间复杂度分析：blablabla

C++ 代码

#include<iostream>

using namespace std;

int f[100010]={0},size[100010]={1},n,m;
//这里是初始化，数组里面存的是自己数组下表的编号
void init()
{
    int i;
    for(i=1;i<=n;i++)
    {
        f[i]=i;
        size[i] = 1;
    }
}

//这是找爹的递归函数，不停地找爹，直到找到祖宗为止，其实就是找犯罪团伙的最高领导人，“擒贼先擒王”原则
int getf(int v)
{
    if(f[v]==v)
    {
        return v;
    }
    else
    {
        //这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的"BOSS"改为最后找到的祖宗的编号，
        //也就是犯罪团伙的最高领导人编号。这样可以提高找到犯罪团伙的最高领导人(其实就是树的祖先)的速度。
        f[v]=getf(f[v]);
        return f[v];
    }
}
//这里是合并两子集合的函数
void merge(int v,int u)
{
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2)//判断两个节点是否在同一个集合中，即是否为同一个祖先
    {
        f[t2]=t1;
        size[t1] += size[t2];
        //“靠左原则”，左边变为右边的BOSS。几把右边的集合，作为左边集合的子集合
        //经过路径压缩以后，将分f[u]的根的值也赋值为v的祖先f[t1]。
    }
}

int main()
{
    cin >> n >> m;
    init();
    while (m -- )
    {
        string op;
        int a, b;
        cin >> op;

        if (op == "C")
        {
            cin >> a >> b;
            merge(a,b);
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (getf(a) == getf(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << size[getf(a)] << endl;
        }
    }


    return 0;
}

2 评论

用户头像
I-AK-IOI   2019-09-14 13:37         踩      回复 
//Author:WFZWF
#include <bits/stdc++.h>
using namespace std;
int n, m, fa[100001], size[100001];
int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    x = get(x), y = get(y);
    fa[x] = y, size[y] += size[x];
}
int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1;
    while (m--) {
        string op;
        int x, y;
        cin >> op;
        if (op == "C") {
            scanf("%d%d", &x, &y);
            merge(x, y);
        } else if (op == "Q1") {
            scanf("%d%d", &x, &y);
            puts(get(x) == get(y) ? "Yes" : "No");
        } else {
            scanf("%d", &x);
            printf("%d\n", size[get(x)]);
        }
    }
}

#帮我看一下

用户头像
小纸条o--o   2019-09-18 11:50         踩      回复 
#include <bits/stdc++.h>
using namespace std;
int n, m, fa[100001], size[100001];
int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    x = get(x), y = get(y);
    if(x!=y)
    fa[x] = y, size[y] += size[x];
}
int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1;
    while (m--) {
        string op;
        int x, y;
        cin >> op;
        if (op == "C") {
            scanf("%d%d", &x, &y);
            merge(x, y);
        } else if (op == "Q1") {
            scanf("%d%d", &x, &y);
            puts(get(x) == get(y) ? "Yes" : "No");
        } else {
            scanf("%d", &x);
            printf("%d\n", size[get(x)]);
        }
    }
}