PTA - 推断学生所属学校的人数（简单的并查集问题）

Jasmine ·

更新时间:2024-09-20

· 727 次阅读

某个比赛现场有来自不同学校的N名学生，给出M对“两人同属一所学校”的关系，请推断学校数量，并找出人数最多的学校

题意其实很简单，但是思路该怎么写呢？
其实这就是一个简单的并查集问题，什么是并查集？

链接：https://blog.csdn.net/zjy_code/article/details/80634149?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase

来源 : zjy_code 的博客

在这里插入图片描述

知道了什么是并查集和并查集的相关操作后，就可以看懂下面的代码了

/* 
    并查集: 
*/
#include 
using namespace std;

const int maxn = 1005;
int f[maxn], student_num[maxn];  // f 储存每个学校, student_num 储存人数

struct hash_map {  // unordered_map 好像用不了, 所以用一个集合代替了
    string name;
    int x;
}mp[maxn];

int find ( int x ) {  // 找根节点
    if ( f[x] == x ) return x;
    return find ( f[x] );
}

void merge ( int x, int y ) {  // 连接树
    x = find ( x );
    y = find ( y );
    if ( x != y ) {
        f[x] = y;
        student_num[y] += student_num[x];  // x 和 y 与上面一行的顺序相反
    }
}

int main(){
    int n; cin >> n;
    string str, a, b;
    // unordered_map mp;
    for ( int i = 1; i <= n; i++ ) {
        f[i] = i;  // 假设起始有 n 个学校,
        student_num[i] = 1;  // 假设起始就有n 间学校, 每个学校 1 个人
    }
    for ( int i = 1; i > str;
        mp[i].name = str;
    mp[i].x = i;
    }

    int m; cin >> m;
    while ( m-- ) {
        cin>>a>>b;
    int i;  // 找 a 的下标
        for ( i = 1; mp[i].name != a; i++ );
    int j;  // 找 b 的下标
        for ( j = 1; mp[j].name != b; j++ );

        merge ( mp[i].x, mp[j].x );
    }
    int school_num = 0, max_student = 0;
    for ( int i = 1; i <= n; i++ ) {
        if ( f[i] == i) {  // 代表有多少颗树
            school_num++;
            max_student = max ( max_student, student_num[i]);  // 找最多的人数
        }
    }
    cout << school_num << " " << max_student;
    return 0;
}

在这里插入图片描述