#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

struct tree {
    int key;
    tree* left;
    tree* right;
} *root = NULL;

const int n = 10;//максимум брой елементи в граф
int maxBrojIzhodVrazki = 0;


struct link //spisak ot grafa
{
    int key;
    link *next;
}
*gr[n]; //масив от указатели

void inti_graph(link *gr[n]);
int search_node_graph(link *gr[n], char c);
int search_arc_graph(link *gr[n], char c1, char c2);
void add_node_graph(link *gr[n], char c);
void add_arc_graph(link *gr[n], char c1, char c2);
void obhozdane_graph(link *gr[n]);

void main()
{
    inti_graph(gr);

    char elem_1 = 'a';
    char elem_2 = 'a';

    cout << "Vavedete vrazka mezdu dva elementa: " << endl;
    cout << "Element 1: ";
    cin >> elem_1;
    cout << "Element 2: ";
    cin >> elem_2;

    add_arc_graph(gr, elem_1, elem_2);

    string answear = "";
    while (true)
    {
        cout << "Zelaete li da vavedete oshte vrazki (z - ne): ";
        cin >> answear;

        if (answear == "z")
        {
            break;
        }
        else
        {
            cout << "Element 1: ";
            cin >> elem_1;
            cout << "Element 2: ";
            cin >> elem_2;
            add_arc_graph(gr, elem_1, elem_2);
        }
    }

    obhozdane_graph(gr);
    cout << "Rang na grafa: " << maxBrojIzhodVrazki << endl;
}


// Инициализация
void inti_graph(link *gr[n])
{
    for (int i = 0; i < n; i++)
        gr[i] = NULL;
}

//Търсене на връх
int search_node_graph(link *gr[n], int c)
{
    int flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (gr[i])
        {
            if (gr[i]->key == c)
                flag = 1;
        }
    }
    return flag;
}

//Търсене на дъга
int search_arc_graph(link *gr[n], char c1, char c2)
{
    int flag = 0;

    if (search_node_graph(gr, c1) && search_node_graph(gr, c2))
    {
        int i = 0;

        while (gr[i]->key != c1)
            i++;

        link *p = gr[i];

        while (p->key != c2 && p->next != NULL)
            p = p->next;

        if (p->key == c2)
            flag = 1;
    }

    return flag;
}

//Добавяне на връх
void add_node_graph(link *gr[n], char c)
{
    if (search_node_graph(gr, c))
        cout << "Sashtestvuva vruh s tazi stojnost" << endl;
    else
    {
        int i = 0;
        while (gr[i] && i < n)
            i++;

        if (gr[i] == NULL)
        {
            gr[i] = new link();
            gr[i]->key = c;
            gr[i]->next = NULL;
        }
        else
            cout << "Prepalvane na strukturata" << endl;
    }
}

//добавяне на дъга
void add_arc_graph(link *gr[n], char c1, char c2)
{
    if (search_arc_graph(gr, c1, c2))
        cout << "Dagata veche sashtestvuca";
    else
    {
        if (!search_node_graph(gr, c1))
            add_node_graph(gr, c1);
        if (!search_node_graph(gr, c2))
            add_node_graph(gr, c2);

        int i = 0;
        while (gr[i]->key != c1)
            i++;

        link *p = new link;
        p->key = c2;
        p->next = gr[i]->next;
        gr[i]->next = p;
    }
}

void obhozdane_graph(link *gr[n])
{
    for (int i = 0; i < n; i++)
    {
        if (gr[i])
        {
            link *p = gr[i];

            int brojIzhodVrazki = -1;

            while (p)
            {
                p = p->next;
                brojIzhodVrazki++;
            }

            if (brojIzhodVrazki > maxBrojIzhodVrazki) {
                maxBrojIzhodVrazki = brojIzhodVrazki;
            }

            brojIzhodVrazki = 0;
        }
    }
}

int search_node_graph(link *gr[n], char c)
{
    int flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (gr[i])
        {
            if (gr[i]->key == c)
                flag = 1;
        }
    }
    return flag;
}