并查集（Union Find ） P

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 find 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 finds all the suspects.

Input

The input file 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（表示有m组数据），接下来便是m组数据，每一组数据表示同组人的个数及其编号，同组的人才能被传染,0为传染源。
output：最多能被传染的人数、

方法：并查集
AC代码：

#include<iostream>

#define maxn 30005

using namespace std;

int p[maxn];

int jishu[maxn];

int fa;

int findx(int x)

{

    int temp=x;

    return x==p[x]?x,p[temp]=x:findx(p[x]);

}

int myunion(int son, int fa){

    int s=findx(son),f=findx(fa);

    if(s!=f){

         p[s]=f;

         jishu[f]+=jishu[s];

    }

    return ;

}

int main ()

{

    int n,m,t;

    while(cin>>n>>m&&(n+m)!=)

    {

        for(int i=;i<=n;i++)

            {

                p[i]=i;

                jishu[i]=;

            }

        while(m--)

        {

            int num;

            cin>>t;

            for(int i=;i<t;i++)

            {

                cin>>num;

                if(i) myunion(num,fa);

                fa=num;

            }

        }

        cout<<jishu[findx()]<<endl;;

    }

}

这个真的很难理解！

首先

100 4

2 1 2

5 10 13 11 12 14

2 0 1

2 99 2
将每一组数据写成一棵树，若有交叉出现，便合并成一棵树
即：用一个数组，先初始化为a【i】=i,然后将同一组数用父子关系联系起来，即 a【son】=father，形成一棵单独的树。
例如：第一组把1作为根，即father，即a【1】=1不变，a【2】=1，即 a【son】=father，第二，三组以此类推。
但是要注意的是，当出现已经有过父子关系的节点时，要分情况讨论。
例如：第一组的1，已经作为2的father，第三组又出现1，作为0的son.这个时候我们不能单纯的写成两棵独立的树，便要合并union。
方法：判断并合并

int myunion(int son, int fa){

    int s=findx(son),f=findx(fa);     //找到祖宗

    if(s!=f){                        //判断祖宗是否一致，一致根本就不用管

         p[s]=f;                     //不一致便合并，串起来

         jishu[f]+=jishu[s];

    }

    return ;

}

例如：

第一组之后：p【1】=1，p【2】=1

第三组之后：p【0】=0，p【1】=0，p【2】=0（调用了findx函数，进行了路径压缩）

第四组之后：p【0】=99，p【2】=0，p【99】=99

巴特西

并查集（Union Find ） P - The Suspects

最新文章

热门文章

巴特西

并查集 （Union Find ） P - The Suspects

最新文章

热门文章

并查集（Union Find ） P - The Suspects