search

pangfengliu / programmingtasks

programming tasks from my courses
68 stars 17 forks source link

Disjoint Clubs #352

Open littlehug opened 6 years ago

littlehug commented 6 years ago

Write a program to pick the clubs that have no member in common.

Task Description

There are N clubs for 64 persons to join. Each person has an id from 0 to 63. Each person can join as many clubs as he wishes. After people join the clubs, you need to pick K clubs so that no two clubs have any person in common. That is, the member list of any two chosen clubs are disjoint. For example, if we have five clubs A, B, C, D and E. The following are the member list for each club:

club id club name member list
0 club A 6, 7, 9
1 club B 11, 13, 17
2 club C 6, 13, 15
3 club D 0, 4, 5, 8, 33, 63
4 club E 10

The members of club A and club B are disjoint since they do not have any common member. However, the members of club A and club C are not disjoint since they have common member 6. Thus, we have four clubs A, B, D, E whose members are disjoint.

Note that we need to choose K clubs in alphabetic (dictionary) order if there are more than one solutions. For example, if K = 4, obviously we have only one solution (A, B, D, E). If K = 3, we have four solutions (A, B, D), (A, B, E), (A, D, E), (B, D, E) and we will choose the solution (A, B, D) since it has the least alphabetic order.

Write a program to pick out K clubs that have no member in common, and output K clubs with their id which is from 0 to N-1. It is guaranteed that there exists a solution.

Subtask

Input Format

The input contains only one test case. The first line contains two integers N and K, where N is the number of the clubs, and K is the number of disjoint clubs we will pick. The rest of input are the member information for each club. Each line contains a sequence of integers. The first integer M in each line is the number of members, and it is followed by the member list of the club. It is guarantee that there is at least one member for each club.

Output Format

Print ids of K clubs which have no member in common. Note that the id number should be print in increasing order.

Sample Input 1

5 2
3 6 7 9
3 11 13 17
3 6 13 15
6 0 4 5 8 33 63
1 10

Sample Output 1

0
1

Sample Input 2

5 3
3 6 7 9
3 11 13 17
3 6 13 15
6 0 4 5 8 33 63
1 10

Sample Output 2

0
1
3

Sample Input 3

82 24
5 31 33 42 44 53
1 59
7 29 37 42 43 44 50 58
10 3 10 18 24 32 39 46 50 56 60
1 10
1 29
10 2 11 17 27 31 39 49 50 55 63
2 16 18
2 57 61
7 30 32 35 45 47 49 59
2 18 20
2 16 17
7 33 40 43 51 57 59 62
5 28 32 40 48 57
1 7
1 56
1 37
3 51 52 62
12 19 23 26 29 30 35 36 43 45 55 60 61
6 32 35 42 51 54 59
6 29 38 44 49 52 62
1 16
2 49 51
8 24 27 30 34 41 49 50 57
4 44 46 55 59
10 17 24 26 27 31 32 38 44 46 55
2 57 58
4 42 49 51 53
1 54
11 3 9 13 19 24 29 35 45 52 55 60
1 4
9 19 26 29 33 39 45 50 54 58
5 44 46 48 58 63
2 10 14
2 53 58
2 7 12
9 21 22 23 32 37 41 45 51 60
11 9 19 23 31 36 41 45 55 57 58 59
1 59
8 29 39 42 46 56 58 59 62
3 54 60 63
1 50
3 43 53 59
2 48 52
2 24 25
3 51 61 62
1 28
5 27 37 45 55 59
8 13 22 24 33 39 49 55 62
11 5 15 20 22 24 31 39 49 52 59 63
2 32 35
4 37 41 45 55
12 6 7 17 18 26 28 35 44 47 50 56 58
3 48 52 59
1 29
1 12
2 19 23
11 14 19 28 31 33 35 37 43 51 58 59
9 15 16 21 31 38 47 48 54 56
1 63
7 16 22 30 37 44 47 55
6 29 39 44 47 54 63
1 29
1 61
7 49 52 53 56 58 61 62
3 39 47 55
2 52 59
5 38 44 47 55 57
7 25 31 39 49 57 59 61
4 37 47 53 63
5 53 57 59 60 63
11 0 1 10 12 17 20 30 40 42 51 61
4 52 56 57 63
1 60
3 37 44 48
7 34 38 40 43 53 59 63
5 48 49 53 54 61
5 39 43 50 54 62
8 41 42 44 49 50 54 55 59
2 62 63
1 42
12 5 11 15 17 22 30 31 41 48 51 58 60

Sample Output 3

0
1
4
5
10
11
14
15
16
22
26
28
30
41
43
44
46
50
55
56
59
63
65
73