parent_ID Gender Name Surname parent1_ID parent2_ID
0 (indicates end of file)

Count TribeFather(or TribeMother depending on the gender) Name Surname

#include <iostream>
#include <fstream>
using namespace std;

class Node
{
public:
    int PK;
    char Gender;
    char Name[31];
    char Surname[31];
    int P1PK;
    int P2PK;
    int kids; //for storing members of tribe
    int index;
    int lastVisited;

    //nodes to parents
    Node * P1;
    Node * P2;


    Node(fstream & file)
    {
        file >> PK;
        file >> Gender;
        file >> Name;
        file >> Surname;
        file >> P1PK;
        file >> P2PK;
        P1 = NULL;
        P2 = NULL;
        kids = 1;
        lastVisited = -1;
    };
};

void countVisits(Node * vertex, Node * ancestor, int vertCount, Node ** vertices, int ** adjMatrix)
{
    if (vertex != NULL)
    {
        if (vertex->lastVisited!=ancestor->index)
        {

            // Depth first search, for each original parent increment size of the tribe
            for (int i = 0; i < vertCount; i++)
            {
                //if edge exists from parent to children
                if (adjMatrix[vertex->index][i] == 1)
                {
                    countVisits(vertices[i], ancestor, vertCount, vertices, adjMatrix);
                    ancestor->kids++;
                }
            }
            vertex->lastVisited = ancestor->index;
        }
    }
}

int main()
{
    //read all the info into array
    fstream file;
    file.open("tribe.in", ios::in);
    char temp[100];
    int vertCount = 0;

    file.getline(temp, 100);
    //count how many objects in the file

    do{
        file.getline(temp, 100);
        vertCount++;
    }while (temp[0] != '0');

    //reset to beginning
    file.clear();
    file.seekg(0, ios::beg);

    //pointer array, which points to graph peaks
    Node ** vertices = new Node*[vertCount];
    //fill in the array
    for (int i = 0; i < vertCount; i++)
    {
        vertices[i] = new Node(file);
        vertices[i]->index = i; //
    }

    //arrange parent pointers
    for (int i = 0; i < vertCount; i++)
    {
        for (int j = 0; j < vertCount; j++)
        {
            if (vertices[i]->P1PK == vertices[j]->PK)
            {
                vertices[i]->P1 = vertices[j];
            }

            if (vertices[i]->P2PK == vertices[j]->PK)
            {
                vertices[i]->P2 = vertices[j];
            }
        }
    }



    //create matrix
    int **adjMatrix = new int *[vertCount];
    for (int i = 0; i < vertCount; i++)
    {
        adjMatrix[i] = new int[vertCount];
        for (int j = 0; j < vertCount; j++) adjMatrix[i][j] = 0;
    }

    //fill in the matrix
    for (int i = 0; i < vertCount; i++)
    {
        if (vertices[i]->P1 != NULL) adjMatrix[vertices[i]->P1->index][i] = 1;
        if (vertices[i]->P2 != NULL) adjMatrix[vertices[i]->P2->index][i] = 1;
    }

    //Depth first counting children
    for (int i = 0; i<vertCount; i++)
    {
        if (vertices[i]->P1 == NULL && vertices[i]->P2 == NULL)
        {
            countVisits(vertices[i], vertices[i], vertCount, vertices, adjMatrix);
        }
    }

    //Find parent with largest count of children
    int kidsCount = 0;
    for (int i = 0; i < vertCount; i++)
    {
        if (vertices[i]->kids > vertices[kidsCount]->kids)
        {
            kidsCount = i;
        }
        else if ((vertices[i]->kids == vertices[kidsCount]->kids) && (vertices[i]->PK < vertices[kidsCount]->PK))
        {
            kidsCount = i;
        }
    }

    //writing result to the output file
    fstream file2;
    file2.open("tribe.out", fstream::out);
    if (vertCount>0)
    {

        file2 << vertices[kidsCount]->kids << ' ';
        if (vertices[kidsCount]->Gender == 'W') file2 << "TribeMother" << ' ';
        else file2 << "TribeFather" << ' ';
        file2 << vertices[kidsCount]->Name << ' ' << vertices[kidsCount]->Surname;
    }
    file2.close();
    file.close();

    //memory clean-up
    for (int i = 0; i < vertCount; i++)
    {
        delete vertices[i];
    }
    delete vertices;

    for (int i = 0; i < vertCount; i++)
    {
        delete adjMatrix[i];
    }

    delete adjMatrix;
    return 0;
}

1 M Adam Father 0 0
2 W Liza Daughter 1 0
3 M John Son 0 1
4 M Oho Child 2 3
0

4 TribeFather Adam Father

5 TribeFather Adam Father