今天的非常简单的并查集入门题目


大意:给人数和群体数,看和患者直接或间接在一个群体里的人数
思路:把人都放在树里,看看每一个人和parent[0]是否相同即可。

代码在此

#include <iostream>
int const MaxSize = 3e4+10;
using namespace std;

int num,numg;
int parent[MaxSize];

void init(){
    for(int i = 0;i <= num;i++){
        parent[i] = i;
    }
    return;
}

int find(int x){
    if(x == parent[x]) return x;
    else{
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void union_(int x,int y){
    int x_root = find(x);
    int y_root = find(y);
    if(x_root == y_root) return;
    else parent[x_root] = y_root;
    return;
}

int main()
{
    while(scanf("%d %d",&num,&numg) && (num || numg)){
        init();
        for(int i = 0;i < numg;i++){
            int numr;
            cin>>numr;
            int x,y;
            for(int j = 1;j <= numr;j++){
                cin>>y;
                if(j == 1) x = y;
                else{
                    union_(x,y);
                }
            }
        }
        int root = find(0),ans = 0;
        for(int i = 0;i < num;i++){
            if(find(i) == root) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

我的第一道自己真正动手的用到树的题目
大一快过去了,我终于跟树打上交道了www


大意:中文的翻译很好理解,就是朋友的朋友是朋友,不是朋友不坐在一张桌子上,问要几张桌子。
思路:也是很基础的题目,就按部就班的把一个个连成树就行啦~不在一棵树就要多一张桌子。

代码在此

#include <iostream>
#include <string.h>
using namespace std;
int const MaxSize = 1010;

int parent[MaxSize];
bool is_table[MaxSize];
int num;
void init(){
    for(int i = 1;i <= num;i++){
        parent[i] = i;
    }
    return;
} 

int find(int x){
    if(x != parent[x])
        parent[x] = find(parent[x]);
    return parent[x];
}

void union_(int x,int y){
    int x_root = find(x);
    int y_root = find(y);
    if(x_root == y_root) return;
    else{
        parent[x_root] = find(y);
    }
    return;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int numg;
        cin>>num>>numg;
        init();
        memset(is_table,true,sizeof(is_table));
        for(int i = 0;i < numg;i++){
            int a,b;
            cin>>a>>b;
            union_(a,b); 
        }
        int ans = 0;
        for(int i = 1;i <= num;i++){
//            cout<<"find  = "<<find(i)<<endl;
            if(is_table[find(i)]){
                ans++;
                is_table[find(i)] = false;    
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

今天只写了两道简单的算法题,都在刷学校Oj哎 明天考试加油~

Last modification:June 28th, 2020 at 10:01 pm
请赏我杯奶茶,让我快乐长肉