>

粗略并查集2

- 编辑:www.bifa688.com -

粗略并查集2

原创 

The Suspects

必发88手机版,当真是温馨写的啊!


Time Limit: 1000MS   Memory Limit: 20000K
Total Submissions: 42098   Accepted: 20311

题目:

The Suspects

Description

B - The Suspects

POJ - 1611 

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个组的成员个数k和成员
    只要是每组中有一个人得了传染病那么整个组都会有传染病
思路:

            基本并查集模板,参加个数管理间接重回就ok

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
#define maxn 100005
using namespace std;
int fa[maxn],rank[maxn];
void init(int n)
{
    for(int i=0;i<n;i  )
    {
        fa[i]=i;
        rank[i]=1;
    }
}
int find(int x)
{
    if(fa[x]==x)return x;
    else{
        return fa[x]=find(fa[x]);
    }
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return ;
    if(x!=y)
    {
        fa[x]=y;
        rank[y] =rank[x];
    }
    /*if(rank[x]<rank[y])
    {
        fa[x]=y;
        rank[x] =rank[y];
    }
    else{
        fa[y]=x;
        rank[y] =rank[x];
       // if(rank[x]==rank[y])rank[x]  ;
    }
    */
}
int main()
{
    int n,m,k;
    int s[maxn];
    while(cin>>n>>m){
    init(n);
    if(n==0&&m==0)return 0;
    while(m--)
    {
       cin>>k;
       for(int i=0;i<k;i  )
       {
           cin>>s[i];
       }
       for(int i=0;i<k-1;i  )
       {
           unite(s[i],s[i 1]);
       }
    }
    int t=find(0);
    cout<<rank[t]<<endl;
    }
    return 0;
}

PS:
代码极粗略,思路清晰就ojbk,,

 

**Time Limit: 1000MS  Memory Limit: 20000K**

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.

**Total Submissions: 48698  Accepted: 23286**

Input

Description

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.

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003.

Output

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,

For each case, output the number of suspects in one line.

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

Sample Input

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.

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

Input

Sample Output

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.

4
1
1

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

Source

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

Asia Kaohsiung 2003

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

必发88手机版 1必发88手机版 2

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
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 #include <vector>
 7 #define max(a, b) ((a) > (b) ? (a) : (b))
 8 #define min(a, b) ((a) < (b) ? (a) : (b))
 9 
10 inline void read(int &x)
11 {
12     x = 0;char ch = getchar(), c = ch;
13     while(ch < '0' || ch > '9')c = ch, ch = getchar();
14     while(ch <= '9' && ch >= '0')x = x * 10   ch - '0', ch = getchar();
15     if(c == '-')x = -x;
16 }
17 
18 const int MAXN = 100000   10;
19 
20 int n, m, fa[MAXN], ans;
21 
22 int find(int x)
23 {
24     return x == fa[x] ? x : fa[x] = find(fa[x]);
25 }
26 
27 int main()
28 {
29     register int pre,now,tmp,f1,f2;
30     while(scanf("%d %d", &n, &m) && n   m)
31     {
32         ans = 0;
33         for(register int i = 1;i <= n;   i)fa[i] = i;
34         for(register int i = 1;i <= m;   i)
35         {
36             read(tmp);
37             read(pre);   pre;
38             f1 = find(pre);
39             for(register int j = 2;j <= tmp;   j)
40             {
41                 read(now);   now;
42                 f2 = find(now);
43                 fa[f2] = f1;
44             }
45         }
46         f1 = find(1);
47         for(register int i = 1;i <= n;   i)
48         {
49             int k = find(i);
50             ans  = (f1 ==k);
51         }
52         printf("%dn", ans);
53     }
54     return 0;
55 }

Sample Output

POJ1611

4
1
1

 

Source

Asia Kaohsiung 2003

 

此题出自POJ——161一:

 

主题素材大体:

  高校要寻找患了SAHighlanderS一共有微微人,n个学生人数(编号0~n-一),m个协会,每一个协会有k个人,并提交那k个人的号子。

各类学生可以加入四个组织,如若一个组织里面存在3个或七个患病学生,则社团方方面面人都会患有,所以患有组织里面恐怕

存在参预七个组织的病倒学生,那样会推动协会传染,高校供给求出患病人数,当然,定义编号为0的学习者是第二个患病学生。

  输入:第贰行n(学生人数)和m(组织数),接下去m行,每行第3个数代表k,接下去k个数代表在座此协会的上学的儿童的编号,

  n==m==0时表示结束。

  输出:患病学生人数

只顾:能够输入多组数据,等终结输入后再一同分行输出结果。

 

解题思路:(并查集算法具体思路不再赘言,实际情况查看:)

  并查集,大家把每一种协会的学生的号码整合起来放在同等棵树上,若三个学生参与了多少个组织,则他所参组织的多棵树会被合并起来成为一棵,**如此那般结尾只供给找寻号码为0的学员所在的树的结点数正是患有学生的总人口了。**

  值得注意的是,代码中对寻找根节点的算法进行了优化!

  原来只是独自的追寻有些结点所在树的根节点,并从未改换数的构造:

  return node==student[node]?node:find_Father(student[node]); 

  优化后,改造了树的布局,将结点至根节点的链上的享有结点直接指向了根节点,大大方便了下一次重新寻觅的功效!

  static int find_Father(int node) {    //寻找根节点
        /*
        return node==student[node]?node:find_Father(student[node]); 
        */

        if(node!=student[node]) {
            student[node]=find_Father(student[node]);    
            //状态压缩,将结点node到根节点这条链上的结点直接指向根节点,优化下次寻找根节点的时间
        }
        return student[node];

    }

Java代码:

import java.util.*;

public class TheSuspects {

    static int n;    //学生数量
    static int m;    //组的数量
    static int student[];
    static int book[];

    static int find_Father(int node) {    //寻找根节点
        /*
        return node==student[node]?node:find_Father(student[node]); 
        */

        if(node!=student[node]) {
            student[node]=find_Father(student[node]);    
            //状态压缩,将结点node到根节点这条链上的结点直接指向根节点,优化下次寻找根节点的时间
        }
        return student[node];

    }

    public static void main(String[] args) {

        Scanner reader=new Scanner(System.in);
        ArrayList list=new ArrayList();
        int count=0;

        while(reader.hasNext()) {

            n=reader.nextInt();
            m=reader.nextInt();
            if(n==0 && m==0) {
                break;
            }
            student=new int[n];
            book=new int[n];
            for(int i=0;i<n;i  ) {
                student[i]=i;    //学生指向自己
                book[i]=1;    //每个学生为1个结点
            }
            for(int i=1;i<=m;i  ) {
                int k=reader.nextInt();
                int node_One=reader.nextInt();    //输入k个结点中的第一个
                for(int j=1;j<=k-1;j  ) {
                    int node_Two=reader.nextInt();
                    int father_One=find_Father(node_One);    //找出父节点
                    int father_Two=find_Father(node_Two);
                    if(father_One!=father_Two) {
                        student[father_Two]=father_One;    //合并
                        book[father_One] =book[father_Two];    //book[根节点]存储其所在树的结点数,每有一个学生加入此数,总结点数 1
                    }
                }
            }
            list.add(book[find_Father(0)]);    //求0所在树的结点个数
            count  ;

        }
        for(int i=0;i<count;i  ) {
            System.out.println(list.get(i));
        }
    }

}

POJ截图:

必发88手机版 3

23:31:36

2018-07-18

本文由必发88手机版发布,转载请注明来源:粗略并查集2