#include <iostream>
#include <fstream>
#include <graphics.h>
#include <cmath>
#include <string.h>
#include <stdio.h>

using namespace std;

int coord_centre[50][50],viz[20];

ifstream fin("graf.in");
#define PI 3.1415

int m[7];

void Init_Graf(int a[50][50])
{
    for(int i=0;i<50;i ++)
        for(int j=0;j<50;j++)
            a[i][j]=0;
}

void Citire_muchii(int &n,int a[50][50])
{
    Init_Graf(a);
    fin>>n ;
    int i,j;
    while(fin>>i>>j)
        a[i][j]=a[j][i]=1;
}

void Afisare_MA(int n,int a [50][50])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
}

void deseneaza_graf(int a[50][50], int n)
{
    initwindow(1000,600);
    int R=200,r=40;
    double x=500,y=300,xi,yi;
    char G[50];
    double alfa;
    alfa=2*PI/n;
    char pattern[8] = {0x00, 0x70, 0x20, 0x27, 0x24, 0x24, 0x07, 0x00};
    for(int i=0;i<n;i++)
    {
        xi=x+R*sin(i*alfa);
        yi=y+R*cos(i*alfa);
        coord_centre[i+1][0]=xi;
        coord_centre[i+1][1]=yi;
        setcolor(RED);
        circle(xi,yi,r);
        setfillstyle(SOLID_FILL,MAGENTA);
        fillellipse(xi,yi,r,r);
        setfillstyle(SOLID_FILL,CYAN);
        fillellipse(xi,yi,r-7,r-7);
        char s[3];
        itoa(i+1,s,10);
        setcolor(7);
        outtextxy((xi-r/2+17),(yi-r/2)+10,s);
    }
    char S[3];
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            if(a[i][j]==1)
            {
                setcolor(CYAN);
                line(coord_centre[i][0],coord_centre[i][1],coord_centre[j][0],coord_centre[j][1]);
                delay(500);
            }
}

void deseneaza_bf(int a[50][50], int n)
{
    initwindow(1000,1000);
    int R=200,r=40;
    double x=600,y=400,xi,yi;

    double alfa= 2*3.1415/n;
    for(int i=0; i<n; i++)
    {
        xi=x+R*sin(i*alfa);
        yi=y+R*cos(i*alfa);
        coord_centre[i+1][0]=xi;
        coord_centre[i+1][1]=yi;
        setcolor(RED);
        circle(xi,yi,r);
        ///setfillpattern(pattern, MAGENTA);
        setfillstyle(SOLID_FILL,MAGENTA);
        fillellipse(xi,yi,r,r);
        ///setfillpattern(pattern, CYAN);
        setfillstyle(SOLID_FILL,CYAN);
        fillellipse(xi,yi,r-7,r-7);
        char s[3];
        itoa(i+1,s,10);
        setcolor(7);
        outtextxy((xi-r/2+17),(yi-r/2)+10,s);
    }
}


void CitireLant(int v[50],int &l)
{
    int i=0,nod;
    cout<<"Dati o secventa de noduri care se termina cu 0:";
    cin>>nod;
    while(nod)
    {
        v[i++]=nod;
        cin>>nod;
    }
    l=i;
}

int VerificareLant(int v[50], int l, int a[50][50], int n)
{
    int i,j;
    for(i=0;i<l;i++)
        if(v[i]>n)
            return 0;
    for(i=0;i<l-1;i++)
        if(a[v[i]][v[i+1]]==0)
            return 0;
    return 1;
}

int LantElementar(int v[50], int l, int a[50][50], int n)
{
    if(VerificareLant(v,l,a,n))
    {
        for(int i=0;i<l;i++)
            for(int j=i+1;j<l;j++)
                if(v[i]==v[j])
                    return 0;
        return 1;
    }
    else
        return 0;
}

int LantSimplu(int v[50], int l, int a[50][50], int n)
{
    if(VerificareLant(v,l,a,n))
    {
        for(int i=0;i<l-1;i++)
            for(int j=i+1;j<l-1;j++)
                if((v[i]==v[j] && v[i+1]==v[j+1]) || (v[i]==v[j+1] && v[i+1]==v[j]))
                    return 0;
        return 1;
    }
    else
        return 0;
}

void deseneaza_lant(int lant[50], int lg, int a[50][50], int n)
{
    initwindow(1000,1000);
    int R=200,r=40;
    double x=500,y=300,xi,yi;
    char G[50];
    int coord_centre[50][50];
    ///setcolor(YELLOW);
    ///circle(600,400,R);
    double alfa = 2*PI/n;
    char pattern[8] = {0x00, 0x70, 0x20, 0x27, 0x24, 0x24, 0x07, 0x00};
    for(int i=0;i<n;i++)
    {
        xi=x+R*sin(i*alfa);
        yi=y+R*cos(i*alfa);
        coord_centre[i+1][0]=xi;
        coord_centre[i+1][1]=yi;
        setcolor(RED);
        circle(xi,yi,r);
        ///setfillpattern(pattern, MAGENTA);
        setfillstyle(SOLID_FILL,MAGENTA);
        fillellipse(xi,yi,r,r);
        ///setfillpattern(pattern, CYAN);
        setfillstyle(SOLID_FILL,CYAN);
        fillellipse(xi,yi,r-7,r-7);
        char s[3];
        itoa(i+1,s,10);
        setcolor(7);
        outtextxy((xi-r/2+17),(yi-r/2)+10,s);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            if(a[i][j]==1)
            {
                setcolor(CYAN);
                line(coord_centre[i][0],coord_centre[i][1],coord_centre[j][0],coord_centre[j][1]);
                delay(500);
            }
    char s[200], aux[5];
    strcpy(s, "Lantul: ");
    setcolor(YELLOW);
    if(VerificareLant(lant,lg,a,n)==1)
        for(int i=0;i<lg-1;i++)
        {
            itoa(lant[i], aux, 10);
            strcat(s,aux);
            strcat(s, " ");
            line(coord_centre[lant[i]][0], coord_centre[lant[i]][1], coord_centre[lant[i+1]][0], coord_centre[lant[i+1]][1]);
            delay(500);
        }
    itoa(lant[lg-1],aux,10);
    strcat(s,aux);
    outtextxy(0,200,s);
    if(LantElementar(lant,lg,a,n))
        strcpy(s,"Lantul este elementar");
    else
        strcpy(s,"Lantul este neelementar");
    outtextxy(0,250,s);
    if(LantSimplu(lant,lg,a,n))
        strcpy(s,"Lantul este simplu");
    else
        strcpy(s,"Lantul este compus");
    outtextxy(0,300,s);
}

void BF(int a[50][50],int n,int nodstart)
{
    double alfa= 2*3.1415/n;
    double x=600,y=400,xi,yi;
    int R=200,r=40;
    int parc[50], viz[50],in=1,sf=1 ;
    for(int i=0;i<50;i++)
    {
        parc[i]=0;
        viz[i]=0;
    }
    if(nodstart>=1 && nodstart<= n)
    {
        parc[1]=nodstart;
        viz[nodstart]=1;
    }
    while(in<=sf)
    {
        for (int j=1;j<=n;j++)
            if(a[parc[in]][j]==1 && viz[j]==0)
            {
                parc[++sf]=j;
                viz[j]=1 ;
            }
        in++;
    }
    for(int i=1;i<=sf;i++)
    {
        settextstyle(EUROPEAN_FONT, HORIZ_DIR,2);
        xi=x+R*sin((parc[i]-1)*alfa);
        yi=y+R*cos((parc[i]-1)*alfa);
        setfillstyle(SOLID_FILL,YELLOW);
        fillellipse(xi,yi,r-7,r-7);
        char s[3];
        itoa(parc[i],s,10);
        setcolor(7);
        outtextxy((xi-r/2+17),(yi-r/2)+10,s);
        getch();
    }
    for(int i=1;i<=n;i++)
        cout<<parc[i]<<" ";
    cout<<endl;

}

void init(int viz[50])
{
    for(int i=0; i<50; i++)
        viz[i]=0;
}

void DF(int a[50][50],int n,int nodstart)
{
    double alfa= 2*3.1415/n;
    double x=600,y=400,xi,yi;
    int R=200,r=40;
    int st[50],viz[50],vf,ct=1,parc[50];
    init(viz);
    viz[nodstart]=1;
    vf=1;
    st[vf]=nodstart;
    parc[vf]=nodstart;
    cout<<nodstart<<" ";
    while(vf!=0)
    {
        int i=1,k=st[vf];
        while(i<=n && (a[k][i]==0 || (a[k][i]==1 && viz[i]==1)))
            i++;
        if(i==n+1)
            vf--;
        else
        {
            cout<<i<<" ";
            vf++;
            parc[++ct]=i;
            st[vf]=i;
            viz[i]=1;
        }
    }
    for(int i=1; i<=ct; i++)
    {
        settextstyle(EUROPEAN_FONT, HORIZ_DIR, 2);
        xi=x+R*sin((parc[i]-1)*alfa);
        yi=y+R*cos((parc[i]-1)*alfa);
        if(viz[i]==1)
        setfillstyle(SOLID_FILL,YELLOW);
        fillellipse(xi,yi,r-7,r-7);
        char s[3];
        itoa(parc[i],s,10);
        setcolor(7);
        outtextxy((xi-r/2+17),(yi-r/2)+10,s);
        getch();
    }
}
int main()
{
    int x,n,a[50][50],v[50],l,lg,viz[50];
    cout<<"MENIU"<<endl;
    cout<<"1) citire graf"<<endl;
    cout<<"2) afisare matrice"<<endl;
    cout<<"3) afisare graf"<<endl;
    cout<<"4) citire lant"<<endl;
    cout<<"5) afisarea  lantului si tipul lantului"<<endl;
    cout<<"6) BF"<<endl;
    cout<<"7) DF"<<endl;
    cout<<endl;
    cin>>x;
    while(x!=1)
    {
        cout<<"Va rog sa incepeti cu instructiunea 1"<<endl;
        cin>>x;
    }
    while(x!=0)
    {
        if(x==1)
        {
            cout<<"Citire graf"<<endl;
            cout<<endl;
            Citire_muchii(n,a);
        }
        if(x==2)
        {
            cout<<"Afisare matrice de adiacenta"<<endl;
            cout<<endl;
            Afisare_MA(n,a);
            cout<<endl;
        }
        if(x==3)
        {
            cout<<"Afisare graf"<<endl;
            cout<<endl;
            deseneaza_graf(a,n);
        }
        if(x==4)
        {
            closegraph();
            cout<<"Citire lant"<<endl;
            CitireLant(v,l);
            cout<<endl;
            m[4]=1;
        }
        if(x==5)
        {
            if(m[4]==0)
            {
                cout<<"Va rog alegeti instructiunea 4 inaintea instructiunii 5"<<endl;
                cin>>x;
            }
            cout<<"Afisare lant"<<endl;
            if(VerificareLant(v,l,a,n))
                deseneaza_lant(v,l,a,n);
            else
                cout<<"Nu este lant\n"<<endl;
            cout<<endl;
        }
        if(x==6)
        {
            cout<<"BF"<<endl;
            closegraph();
            for (int i=1;i<=n;i++)
            {
                deseneaza_bf(a,n);
                settextstyle(DEFAULT_FONT,HORIZ_DIR,20);
                outtextxy(10,10,"BF(");
                char s[3];
                itoa(i,s,10);
                setcolor(7);
                outtextxy(200,10,s);
                outtextxy(335,10,")");
                BF(a,n,i);
                getch();
                cleardevice();
                closegraph();
            }
            cout<<endl;
        }
        if(x==7)
        {
            cout<<"DF"<<endl;
            closegraph();
            cout<<endl;
            for(int i=1;i<=n;i++)
            {
                deseneaza_bf(a,n);
                settextstyle(DEFAULT_FONT,HORIZ_DIR,20);
                outtextxy(10,10, "DF(");
                char s[3];
                itoa(i,s,10);
                setcolor(7);
                outtextxy(200,10,s);
                outtextxy(335,10,")");
                DF (a,n,i);
                getch();
                cleardevice();
                closegraph();
                cout<<endl;
            }
            cout<<endl;
        }
        cin>>x;
    }
    return 0;
}