Bakground Information: Input starts with two integers n and m, (1 name == toFind) return this; else { for (Node * nodePtr : children) {

Bakground Information:

Input starts with two integers n and m, (1 <= n,m), where n specifiess the number of given extends relationships and m specifies the number of queries. The next n lines each contain one given relationship in the form c1 c2 where c1 and c2 are single-word class names. Following this are m queries, one per line, using the c1 r c2, where r is either "extends" or "isExtendedBy". All class names in the last m lines will appear at least once in the initial n lines. All extends and isExtendedBy relationships between the given classes can be deduced from the n given relationships. Extends relationships can not be circular (apart from the trivial identity "x extends x").

*Question:* For each query, please display the query number (starting at one) and whether the query is true or false. Follow this by a list of all the classes (in alphabetical order) 1 per line, where each class is followed by the names of the classes that it extends.

Sample Input 10 Date Time Appointment Date Calendar Appointment Circle Point Triangle Shape Rectangle Shape Square Rectangle Cone Circle Cylinder Circle Circle Shape 8 Time extends Date Calendar extends Time Cylinder extends Circle Cylinder extends Shape Time isExtendedBy Date Calendar isExtendedBy Time Circle isExtendedBy Cone Time isExtendedBy Shape

Sample Output:

1 false 2 true 3 true 4 true 5 true 6 false 7 true 8 false Appointment Date Time Calendar Appointment Date Time Circle Point Shape Cone Circle Point Shape Cylinder Circle Point Date Time Point Rectangle Shape Shape Triangle Shape

The following code is already complete:

#include

#include

#include

#include

using namespace std;

class Node {

public:

Node(string label) :name(label) {}

Node * find(string toFind) {

Node * findPtr = nullptr;

if (this == nullptr || this->name == toFind)

return this;

else {

for (Node * nodePtr : children) {

findPtr = nodePtr->find(toFind);

if (findPtr != nullptr)

return findPtr;

}

}//else

return nullptr;

}

void print() {

print(0);

}

void addChild(Node *childPtr) {

children.push_back(childPtr);

childPtr->extends.push_back(this);

}

string getName() {

return name;

}

private:

string name;

vector< Node *> children;

vector< Node *> extends;

void print(int level) {

if (this != nullptr) {

for (int i = 0; i < 5 * level; i++)

cout << " ";

cout << this->getName() << endl;

}

for (Node * ptr : children)

ptr->print(level + 1);

}

};

class Program {

public :

Node * find(string name) {

Node * foundPtr = nullptr;

for (Node * nodePtr : classes) {

foundPtr = nodePtr->find(name);

if (foundPtr != nullptr)

return foundPtr;

}

return nullptr;

}

void print() {

for (Node * nodePtr : classes) {

nodePtr->print();

cout << "---------- ";

}

}

void add(string childName, string parentName) {

Node * childPtr = find(childName);

Node * parentPtr = find(parentName);

/*if (parentName == "n") {

cout << "adding " << childName << " extends "

<< parentName << endl;

print();

}*/

if (parentPtr == nullptr) {

parentPtr = new Node(parentName);

classes.push_back(parentPtr);

if (childPtr == nullptr) {

childPtr = new Node(childName);

} // both null

parentPtr->addChild(childPtr);

}// parent Null, but child not in tree

else { // parent is already in the tree

if (childPtr == nullptr)

childPtr = new Node(childName);

parentPtr->addChild(childPtr);

}

for (int i = 0; i < classes.size(); i++)

if (classes[i] == childPtr)

classes.erase(classes.begin() + i);

}//add

private:

vector classes;

};

int main() {

Program program;

string name1, name2;

int numPairs;

cin >> numPairs;

for (int i = 0; i < numPairs; i++) {

cin >> name1 >> name2;

program.add(name1, name2);

//program.print();

}

program.print();

return 0;

}