首页 > 其他分享 >8.13

8.13

时间:2023-08-13 21:12:54浏览次数:36  
标签:pre cnt int scanf ++ find 8.13

今天看科目四的题目明天去考试

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 10005
int n, k, q;                    // n:已知小圈子的个数 k:小圈子里的人数 q:查询次数
int x, y;                       // x:第一个人代表小圈子 y:小圈子的其他人
int i, j, l;                    // 遍历
int cnt1 = 0, cnt2 = 0;         // cnt1:社区的总人数 cnt2:互不相交的部落的个数
int a, b;                       // 一对被查询的人的编号
int cnt[max];                   // 部落数组
int pre[max];                   // 并查集数组
void init();
int find(int x);
void Union(int a, int b);
int main()
{
    // 初始化
    memset(cnt, 0, sizeof(cnt));
    init();

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%d %d", &k, &x);
        cnt[x] = 1;
        for (j = 1; j < k; j++)
        {
            scanf("%d", &y);
            cnt[y] = 1;
            Union(x, y);
        }
    }
    // 求 社区的总人数 和 互不相交的部落的个数
    for (i = 0; i < max; i++)
    {
        // cnt[i]不为0,说明i存在,及人数+1
        if (cnt[i]) 
        {
            cnt1++;
            // pre[i] == i 说明改部落未与其他部落互通
            if (pre[i] == i)
                cnt2++;
        }
    }
    printf("%d %d\n", cnt1, cnt2);

    scanf("%d", &q);
    for (i = 0; i < q; i++)
    {
        scanf("%d %d", &a, &b);
        if (find(a) == find(b))
            printf("Y\n");
        else
            printf("N\n");
    }
    return 0;
}

void init()
{
    for (int i = 0; i < max; i++)
    {
        pre[i] = i;
    }
}

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

void Union(int a, int b)
{
    if (b == -1)
        return;
    int f_a = find(a);
    int f_b = find(b);
    if (f_a != f_b)
    {
        pre[f_a] = f_b;
    }
}

 

标签:pre,cnt,int,scanf,++,find,8.13
From: https://www.cnblogs.com/xuxingkai/p/17627270.html

相关文章

  • 闲话8.13
    今天上午打了一场模拟赛,被一群邢紫藤暴打了......
  • 【闲话】08.13.23
    08.13闲话这几天都好冷清啊,头图也取消罢(你推歌:Leta&可不《ぐるーみぃ》虽然不知道这个p主为啥要用平假名写英语,但是歌还挺可爱的。而且是这个p主的第一首歌,值得鼓励。可不真的很可爱。又被月赛薄纱了:没有学术,累了今天产9oc设定的时候查到脱口秀最开始可以溯源到18世纪英......
  • 8.13日
    我始终相信曲折的路总有它的道理路的尽头也依然是路没有人的一生不起波澜成长的路上总有要经历的地方所以自愈便成了必修的课程流着眼泪吃饭窒息时叹的气躲在卫生间里抽的烟走在夜路上喝的酒人的一生有很多遗憾不理想的成绩失意的爱情没来得及做却做不了的事情上帝俯视并嘲......
  • 【比赛】8.13
    Ⅰ.波状数列考试时想到的是用\(f_{i,0/1}\)表示用了前\(i\)个数,其中第一个数是山峰还是山谷。比较麻烦。之前看题解做的时候,用\(f_{i,j}\)表示用了前\(i\)个数,其中第一个数是\(j\),滚动数组优化一下。点击查看代码#include<bits/stdc++.h>#defineintlonglongc......
  • 8.7-8.13学习总结博客五:Hive进阶与复杂查询
    博客题目:学习总结五:Hive进阶与复杂查询实践内容概要:学习Hive进阶的使用方法,包括复杂查询、数据转换和性能优化等方面的知识。学习资源:推荐的Hive进阶教程、实践案例和性能优化技巧。实践内容:通过编写复杂的Hive查询语句,探索Hive的高级功能和性能优化方法,并分享实践中的挑战和解决......
  • GoodNotes 5 for Mac(笔记软件) 5.8.13中文版
    GoodNotes是一款实用的笔记记录软件,goodnotes不仅仅能够识别pdf文件和图片,而且还支持手写编辑文件功能,goodnotes电脑版能够将手写内容转换为文本,软件能够让用户在导入的PDF......
  • * ./cptable in ./node_modules/[email protected]@xlsx-style/dist/cpexcel.js
    问题项目中用到了xlsx和xlsx-style,但正常安装后,出现以下错误*./cptablein./node_modules/[email protected]@xlsx-style/dist/cpexcel.js1解决方案修改node_modu......
  • 解决 WebSocketClient.js?5586:16 WebSocket connection to 'ws://192.168.13.25:8080
    控制台报错: vue.config.jsVue的配置文件const{defineConfig}=require('@vue/cli-service')module.exports=defineConfig({devServer:{host:'0.0.0......
  • 8.8~8.13总结
    8.9wave【题目描述】海浪分为前浪和后浪,分别用数字0和数字1表示。现在给定一天中n个时段的海浪序列,第i个序列包含$m_i$个海浪。全天海浪序列是n个时段的......
  • 2022.8.13 颓废记录
    Preface最后一天~Content[CF1175E]MinimalSegmentCover给定形如\([l,r]\)的\(n\)条线段。\(m\)次询问,询问每次至少选几条线段才能使它们的并集包含线段\([x,y......