Description
Details
The input to the program consists of two parts. The first line consists of two integers ƒ and q, which
are the number of nuclear families and queries that follow. The next ƒ lines each describe one
nuclear family. These lines are of the form m ƒ ther mother chd1 chd2 . . . chdm, where m
is the number of children in the nuclear family and the remaining elements are names. The last q
lines are pairs of names.
A name is any sequence of non-space characters.
Some definitions for ascertaining relationships:
• p is a 0-descendent of q if p is a child of q.
• p is a k-descendent of q if p is a child of some person r and r is a (k − 1)-descendent of q.
• p is a 0-ancestor of q if p is a parent of q.
• p is a k-ancestor of q if p is a parent of some person r and r is a (k − 1)-ancestor of q.
If two people p and q are related, then they are related in one of the following manners:
• child
p is a child of q if p is a 0-descendent of q
• grandchild
p is a grandchild of q if p is a 1-descendent of q
• great great . . . great
| {z }
n times
grandchild
This is when p is an (n + 1)-descendent of q
• parent
p is a child of q if p is a 0-ancestor of q
• grandparent
p is a grandparent of q if p is a 1-ancestor of q
• great great . . . great
| {z }
n times
grandparent
This is when p is an (n + 1)-ancestor of q
Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034
• cousins and siblings
Let r be the closest common ancestor to p and q; that is, no descendent of r is also an
ancestor of both p and q. Suppose that p is an m-descendent of r and q is an n-descendent
of r. Let s = mn(m, n) and let t = |m − n|. Then, p and q are s-cousins t times removed.
0
th-cousins zero times removed are siblings.
For each query p q, output one of the following lines as appropriate:
• child, grandchild, great great . . . great grandchild
If p is a descendent of q
• parent, grandparent, great great . . . great grandparent
If p is an ancestor of q
• sibling
If p and q are 0-cousins zero times removed
• m-cousin
If p and q are m-cousins zero times removed
• m-cousin removed n
If p and q are m-cousins n times removed
• No relation
If p and q are not related
.Limitations
For any query, there will be at most two closest common ancestors; these will be spouses of each
other.
There will be at most 500 unique names.
What to turn in
Turn in your source code and Makefile. If you use Code::Blocks, turn in a tarball of your project
directory.
2 of 3
Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034
Example Input
13 6
2 bill wilma brenda deb
3 bob.1 diana bob.2 kelly angela
4 mac pearl lloyd bill barb bob.1
2 kelly glenn hilary ashlee
2 bob.2 betty tony nick
1 bob.3 barb bob.4
9 joe.1 nettie ron.1 joe.2 jim.1 bob.3 carol georgia charlie mary.ellen lynette
4 jim.1 mary.ann jim.2 michael bradley brian
3 michael kris max madison mckenna
3 jim.2 connie alex kerri zack
2 ron.1 jackie ron.2 jacob
2 joe.3 helen joe.1 katherine
3 jim.3 emma joe.3 jim.4 george
alex emma
joe.3 ron.2
nick kelly
georgia charlie
deb jacob
tony ashlee
Sample Output
great great great grandchild
great grandparent
0 cousin 1 removed
sibling
no relation
1 cousin
3 of 3
