## CCO '00 P1 - Subsets

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
##### Canadian Computing Competition: 2000 Stage 2, Day 1, Problem 1

In this problem, you will write a program to find the minimal solution to a set of set inequalities. A set inequality has the format X contains S where may be any set name and may be a set name or set element. If is a set name the inequality means that is a superset or equal to . If is an element the inequality means that contains . Sets are named - and contain elements from -.

The first line of input specifies the number of set inequalities (). The next lines each contain one set inequality. For each set name that appears in the input, your program must determine its minimal set: the smallest set of elements that the name must take in order that all of the inequalities hold. Output, in alphabetical order, each set name followed its minimal set, with the elements in alphabetical order, in the format shown below.

#### Sample Input

9
A contains B
A contains c
B contains d
F contains A
F contains z
X contains Y
Y contains X
X contains x
Q contains R

#### Sample Output

A = {c,d}
B = {d}
F = {c,d,z}
Q = {}
R = {}
X = {x}
Y = {x}

• commented on Aug. 8, 2018, 11:42 p.m. edit 2

What is the maximum of in this question?

edit: The maximum of ended up being irrelevant in my solution anyway :p

• commented on May 4, 2017, 9:20 a.m.

Is it guaranteed the sets won't be cyclic? i.e; if A contains B can B contain A

• commented on May 4, 2017, 1:33 p.m. edited

No. They can be cyclic.

• commented on Dec. 19, 2016, 11:08 p.m. edit 2

Is there only 1 element per set? etc: A = {c, d, d}?.

NVM. There's only 1 element per set.

• commented on Feb. 8, 2015, 8:52 p.m. edited

Will the set element always be char's?

• commented on Feb. 9, 2015, 11:38 p.m. edited

Yeah it should be. That's what it said in the instructions.