uva-1197（简单并查集计数）(代码片段)

关键词：

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others. In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they ?nd that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which ?nds all the suspects.
Input
The input ?le contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n ≤ 30000 and 0 ≤ m ≤ 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space. A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0
Sample Output
4 1 1

题目意思：

有n个人，m个学习，每个信息表示k个人曾经是一个团体（一个团体的人只要一人有病，团体所有人都可能患病）现在已经知道0号有病

问你有几个人可能会患病

分析：

简单的计数并查集

最后统计一些和0在一个集合里面的人数就是可能患病总人数

code：

#include <iostream>
#include<algorithm>
#include <cstdio>
#include<cstring>
#include<math.h>
#include<memory>
using namespace std;
typedef long long LL;
#define max_v 30000
int pa[max_v];
int rk[max_v];
int n,m;
void make_set(int x)

    pa[x]=x;
    rk[x]=0;

int find_set(int x)

    if(x!=pa[x])
        pa[x]=find_set(pa[x]);
    return pa[x];

void union_set(int x,int y)

    x=find_set(x);
    y=find_set(y);
    if(x==y)
        return ;
    if(rk[x]>rk[y])
        pa[y]=x;
    else
    
        pa[x]=y;
        if(rk[x]==rk[y])
            rk[y]++;
    

int main()

    while(~scanf("%d %d",&n,&m))
    
        if(n==0&&m==0)
            break;
        for(int i=0;i<=n-1;i++)
            make_set(i);
        for(int i=1;i<=m;i++)
        
            int k;
            scanf("%d",&k);
            int x,y;
            scanf("%d",&x);
            for(int i=1;i<=k-1;i++)
            
                scanf("%d",&y);
                union_set(x,y);
            
        
        int sum=0;
       for(int i=0;i<=n-1;i++)
       
           if(find_set(i)==pa[0])
            sum++;
       
       printf("%d
",sum);
    
    return 0;

jackstrawspoj-1127(简单几何计算+并查集）(代码片段)

InthegameofJackStraws,anumberofplasticorwooden"straws"aredumpedonthetableandplayerstrytoremovethemone-by-onewithoutdisturbingtheotherstraws.Here,weareonlyconcernedwithifvariouspairsofstrawsareconnectedbyapathoftouchingstraws.Youwillbegivenalistoftheendpointsforsomestraws(asiftheyweredumpedonalargepi... 查看详情

并查集(入门)(代码片段)

首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A这道题就是让你判断两两城镇之间是否联通　　如果不联通就要修建一条道路 就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理... 查看详情

并查集模板并查集模板luogu-3367(代码片段)

题目描述简单的并查集模板输入描述第一行包含两个整数N、M，表示共有N个元素和M个操作。接下来M行，每行包含三个整数Zi、Xi、Yi当Zi=1时，将Xi与Yi所在的集合合并当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话... 查看详情

并查集(代码片段)

简单说明：并查集(union-findset)，根据字面意思可以理解为在N个元素中，将属于同一组元素所在的集合合并，期间要反复查找一个元素在哪个集合中，即并+查。处理这类问题时便可以用到这种特殊的数据结构，保证了空间时间不... 查看详情

第四章高级数据结构(代码片段)

...】树状数组241.楼兰图腾【树状数组的基本应用】242.一个简单的整数问题【区间修改/单点查询】243.一个简单的整数问题2【区间修改/区间查询】244.谜一样的牛【快速求排名扩展】线段树1275.最大数【线段树/ 查看详情

c-newsdistribution(并查集）(代码片段)

...ribution Exampleinput 753254021211267output 4414422思路：简单来讲，就是用并查集求每个点所在连通块的大小，有两种写法......写法一：用并查集合并所给边之后，再扫一遍标记每个联通块大小，最后输出，这个写法比较好理解... 查看详情

并查集的小节(代码片段)

...理解的；看了挑战程序竞赛这本后，感觉大佬的思路就是简单，高效，可以首先写几个函数，分部实现各个功能，按照思路：1，格式化数组；2，定义查找函数，便于找根；3，定义联合函数，使需要联合的函数联合在一起，4，... 查看详情

poj2236（并查集）(代码片段)

...问，叫你判断询问的两台电脑之间是否连接。思路：　　简单的并查集做法 查看详情

程序自动分析（并查集+排序）(代码片段)

...y，否则x！=y，如果矛盾，输出NO，否则YES对于k=1，并查集简单操作一下，k=0，如果find(x)==find(y),打个标记，输出NO；有一个需要注意的地方是，对于询问我们要进行sort，使k=1的情况先执行，这样可以保证最后判断的答案正确。#inc... 查看详情

并查集（21.7.20）(代码片段)

...xff0c;首领与小兵，小兵与小兵等之间的关系问题。二.简单实现:这 查看详情

关于最小生成树(并查集)prime和kruskal(代码片段)

...并查集有一定理解的人. 新手可能看不懂吧....并查集简单点说就是将相关的2个数字联系起来比如 房子           1  2  3  4 5  6能通向的房子  查看详情

并查集(代码片段)

主要内容本文主要记录并查集的基本实现方法，并逐步将一些例题填充到文章中。并查集能做什么并查集可以：1.合并集合2.查找两个元素是否在同一个集合内3.集合数量4.确定元素属于哪个集合。完整代码示例classUFpublic:UF();UF(int... 查看详情

并查集+思维——destroyingarray(代码片段)

...问题分析我们知道从并查集中删除元素很难，而合并非常简单。所以我们可以反过来思考，正向删除元素等同于反向添加元素，将结果存起来反向输出即可。每次添加一个元素，更新最大值。很明显新加入的点只影响相邻元素的... 查看详情

markdown并查集(代码片段)

查看详情

golang并查集(代码片段)

查看详情

并查集（unionfind）(代码片段)

...;中文并查集。主要用来解决图论中的连通判断问题，简单抽象问题为：平面上有n个点给定他们之间两两连接关系要求输入任意两个点，判断他们是否能够有一条路径联通算法步骤一旦有连接，就把一个节点设为... 查看详情

并查集（unionfind）(代码片段)

...;中文并查集。主要用来解决图论中的连通判断问题，简单抽象问题为：平面上有n个点给定他们之间两两连接关系要求输入任意两个点，判断他们是否能够有一条路径联通算法步骤一旦有连接，就把一个节点设为... 查看详情

并查集（unionfind）(代码片段)

...;中文并查集。主要用来解决图论中的连通判断问题，简单抽象问题为：平面上有n个点给定他们之间两两连接关系要求输入任意两个点，判断他们是否能够有一条路径联通算法步骤一旦有连接，就把一个节点设为... 查看详情