【PAT甲级】并查集专题复习

迈不过友情╰ 2023-02-23 12:17 145阅读 0赞

博主开始复习PAT甲级了，会做多个复习的专题，会解释需要注意的基本概念和题库相关的满分代码展示。

目的：通过多刷题，多总结回顾，让自己在方法层面还是代码细节达到熟练写出的程度。

形式：思维导图+代码点评

提示：每个人的基础不同，这里不做普适性的建议。我出的专题重点是串联知识，仅供参考。

--------------------

Dijkstra专题近三年考察情况：19年3月第三题

1158之前写过了：[https://blog.csdn.net/allisonshing/article/details/104361040][https_blog.csdn.net_allisonshing_article_details_104361040]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70][]

放出来的都是我优化的liuchuo的源代码，没放出来的就按照她的写法就行。

# 1107. Social Clusters (30) #

[https://pintia.cn/problem-sets/994805342720868352/problems/994805361586847744][https_pintia.cn_problem-sets_994805342720868352_problems_994805361586847744]

#include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    vector<int> father, isRoot;
    int cmp1(int a, int b){return a > b;}
    //我改了下面两个函数，liuchuo版的是非递归的
    int findFather(int x) {
        return x == father[x]? x : (father[x]=findFather(father[x]));
    }
    void Union(int a, int b) {
        father[findFather(a)]=findFather(b);
    }
    int main() {
        int n, k, t, cnt = 0;
        int course[1001] = {0};
        scanf("%d", &n);
        father.resize(n + 1);
        isRoot.resize(n + 1);
        for(int i = 1; i <= n; i++)
            father[i] = i;
        for(int i = 1; i <= n; i++) {
            scanf("%d:", &k);
            for(int j = 0; j < k; j++) {
                scanf("%d", &t);
                if(course[t] == 0)
                    course[t] = i;
                Union(i, findFather(course[t]));
            }
        }
        for(int i = 1; i <= n; i++)
            isRoot[findFather(i)]++;
        for(int i = 1; i <= n; i++) {
            if(isRoot[i] != 0) cnt++;
        }
        printf("%d\n", cnt);
        sort(isRoot.begin(), isRoot.end(), cmp1);
        for(int i = 0; i < cnt; i++) {
            printf("%d", isRoot[i]);
            if(i != cnt - 1) printf(" ");
        }
        return 0;
    }

### 1114 Family Property (25分) ###

[https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288][https_pintia.cn_problem-sets_994805342720868352_problems_994805356599820288]

### 1118 Birds in Forest (25分) ###

[https://pintia.cn/problem-sets/994805342720868352/problems/994805354108403712][https_pintia.cn_problem-sets_994805342720868352_problems_994805354108403712]

[https_blog.csdn.net_allisonshing_article_details_104361040]: https://blog.csdn.net/allisonshing/article/details/104361040
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707175717691.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw==,size_16,color_FFFFFF,t_70
[https_pintia.cn_problem-sets_994805342720868352_problems_994805361586847744]: https://pintia.cn/problem-sets/994805342720868352/problems/994805361586847744
[https_pintia.cn_problem-sets_994805342720868352_problems_994805356599820288]: https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288
[https_pintia.cn_problem-sets_994805342720868352_problems_994805354108403712]: https://pintia.cn/problem-sets/994805342720868352/problems/994805354108403712