#include<iostream>
using namespace std;

const int n = 15; // 15 върха

struct link{
	char key;
	link *next;
} *gr[n];

//1. Инициализация
void init(link *gr[n])
{
	for(int i = 0; i<n; i++)
	{
		gr[i] = NULL;
	}
}
//2. Търсене на връх
bool search_node(link *gr[n], char c)
{
	bool flag = false;
	for(int i = 0; i<n; i++)
	{
		if(gr[i])
		{
			if(gr[i]->key == c)
			{
				flag = true;
			}
		}
	}
	return flag;
}
//3. Търсене на дъга
bool search_arc(link *gr[n], char c1, char c2)
{
	bool 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 = true;

	}
	return flag;
}
//4. Добавяне на връх
void add_node(link *gr[n], char c)
{
	if (search_node(gr, c))
		cout<<"\nExisting node!\n";
	else
	{
		int j=0;
		while (gr[j] && (j<n)) j++;
		if (gr[j]==NULL)
		{
			gr[j]=new link;
			gr[j]->key=c;
			gr[j]->next=NULL;
		}
		else
			cout<<"\nOverflow!\n";
	}
}
//5. Добавяне на дъга
void add_arc(link *gr[n], char c1, char c2)
{
	int i=0;
	link *p;
	if (search_arc(gr, c1, c2))
	{
		cout<<"\nExisting arc!";
	}
	else
	{
		if (!(search_node(gr, c1)))
			add_node(gr, c1);
		if (!(search_node(gr, c2)))
			add_node(gr, c2);
		while (gr[i]->key!=c1)
			i++;
		p=new link;
		p->key=c2;
		p->next=gr[i]->next;
		gr[i]->next=p;
	}
}
//Отпечатване на граф
void list_node(link *gr[n])
{
	cout<<"\n";
	for (int i=0; i<n; i++)
		if (gr[i])
			cout<<gr[i]->key;
	cout<<endl;
}
bool f(char c, link *gr[n])  // забележка функцията е от булев тип
{
	bool is_have = false;
	for(int i = 0; i<n; i++)
	{
		if(gr[i] && gr[i]->key != c)
		{
			is_have = (search_arc(gr, c, gr[i]->key) && search_arc(gr, gr[i]->key, c));
			if(is_have)
			{
				break;
			}
		}
	}
	return is_have;
}
int main()
{
	char c;
	char k;
	int ans;
	bool p = false;
	cout<<"Vavedete varhove na grafa"<<endl;
	do
	{
	cout<<"Menu"<<endl;
	cout<<"1 - Init"<<endl;
	cout<<"2 - Dobavyane na vrah"<<endl;
	cout<<"3 - Dobavyane na daga"<<endl;
	cout<<"4 - Otpechatvane na grafa"<<endl;
	cout<<"5 - Proverka dali ima vrazka ot tipa '->A<-'"<<endl;
	cout<<"6 - izhod"<<endl;
	cout<<"Vavedete svoya izbor"<<endl;
	cin>>ans;
	switch(ans)
	{
	case 1:
		{
			init(gr);
			break;
		}
	case 2:
		{
			cout<<"Vavedete stoynost na vrah ";
			cin>>c;
			cout<<endl;
			add_node(gr,c);
			break;
		}
	case 3:
		{
			cout<<"Vavedete parvia vrah ";
			cin>>c;
			cout<<endl<<"Vavedete vtoria vrah ";
			cin>>k;
			add_arc(gr, c,k);
			break;
		}
	case 4:
		{
			list_node(gr);
			break;
		}
	case 5:
		{
			for(int i = 0; i<n; i++)
			{
				if (gr[i])
				{
					c = gr[i]->key;
					p = f(c, gr);  // флагът присвоява върнатото от ф-та
					if(p)
					{
						cout<<"===Da, ima takava vrazka==="<<endl;
						break;
					}
				}
			}
			if(!p)
				cout<<"===Ne, nqma takava vrazka==="<<endl;
			break;
		}
	}
}while(ans!=6);
return 0;


}