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

using namespace std;

const int n = 10;
int btojElementi = 0;
string connection = "";
bool isCyclic = false;

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


void inti(link *gr[n]);
int search_node(link *gr[n], char c);
int search_arc(link *gr[n], char c1, char c2);
void add_node(link *gr[n], char c);
void add_arc(link *gr[n], char c1, char c2);
void combinationUtil(char data[], int start, int end, int index, int r);
bool isCycle();


void main()
{
    inti(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(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(gr, elem_1, elem_2);
        }
    }

    int r = 3;
    char data[10];

    for (int r = 2; r <= btojElementi; r++)
    {
        combinationUtil(data, 0, btojElementi - 1, 0, r);
    }

    if (isCyclic) {
        cout << "Grafa sadarza primka" << endl;
    }
    else {
        cout << "Grafa ne sadarza primka" << endl;
    }
}

void inti(link *gr[n])
{
    for (int i = 0; i < n; i++)
        gr[i] = NULL;
}

int search_node(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;
}

int search_arc(link *gr[n], char c1, char c2)
{
    int flag = 0;

    if (search_node(gr, c1) && search_node(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(link *gr[n], char c)
{
    if (search_node(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;

            btojElementi++;
        }
        else
            cout << "Prepalvane na strukturata" << endl;
    }
}

void add_arc(link *gr[n], char c1, char c2)
{
    if (search_arc(gr, c1, c2))
        cout << "Dagata veche sashtestvuca" << endl;
    else
    {
        if (!search_node(gr, c1))
            add_node(gr, c1);
        if (!search_node(gr, c2))
            add_node(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 combinationUtil(char data[], int start, int end, int index, int r)
{
    if (index == r)
    {
        for (int j = 0; j < r; j++)
        {
            connection += data[j];
        }

        bool hasCycle = isCycle();

        if (hasCycle)
        {
            isCyclic = true;
        }

        connection = "";
        return;
    }

    for (int i = start; i <= end && end - i + 1 >= r - index; i++)
    {
        data[index] = gr[i]->key;
        combinationUtil(data, i + 1, end, index + 1, r);
    }
}

bool isCycle()
{
    int firstElementIndex = 0;
    int secondElementIndex = 1;

    for (int i = 0; i < connection.length() - 1; i++)
    {
        char firstElement = connection[firstElementIndex];
        char secondElement = connection[secondElementIndex];

        if (search_arc(gr, firstElement, secondElement) == 0) {
            return false;
        }

        firstElementIndex++;
        secondElementIndex++;
    }

    if (search_arc(gr, connection[connection.length() - 1], connection[0]) == 0)
    {
        return false;
    }

    return true;
}