//Tao class stack

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#include<math.h>

#include<iomanip.h>

#include<string.h>

#include<stdlib.h>

int n,a[50][50];

//------------

class Stack

{

      protected:

                struct node

                {

                   void*dataptr;

                   node*next;

                };

                node*head;

                node*tail;

                int count;

      private:

              void copy(const Stack &st);

      public:

             void ErrorHandler();

             Stack();

             Stack(const Stack &st);

             void operator=(const Stack &st);

             virtual int Store(void *item);

             virtual void *Examine();

             virtual void *Retrieve();

             int GetCount();

             virtual void clear();

};

//--------------

void Stack::ErrorHandler()

{

     cout<<"

Loi: Cap phat bo nho";

}

//-----------

void Stack::copy(const Stack &st)

{

     head=NULL;

     tail=NULL;

     node*item;

     item=st.head;

     while(item!=NULL)

     {

       if(head==NULL)

       {

       head=new node;

       if(head==NULL)ErrorHandler();

       tail=head;

       }

       else

       {

           tail->next=new node;

           if(tail->next==NULL)ErrorHandler();

           tail=tail->next;

       }

       tail->dataptr = item->dataptr;

       tail->next=NULL;

       item=item->next;

     }

}

//------------

Stack::Stack()

{head=NULL;tail=NULL;count=0;}

//--------

Stack::Stack(const Stack &st)

{

   copy(st);

}

//----------

void Stack::operator=(const Stack &st)

{

     count=st.count;

     copy(st);

}

//--------

int Stack::Store(void *item)

{

    node*p;

    p=new node;

    if(p==NULL)return 1;

    p->dataptr=item;

    p->next=head;

    head=p;

    count++;

    return 0;

}

//-------------

void *Stack::Examine()

{

     if(count==0)return NULL;

     else{return head->dataptr;}

}

//-----------

void*Stack::Retrieve()

{

  if(count==0)return NULL;

  else

  {

      node*p;

      void *value;

      value=head->dataptr;

      p=head;

      head=p->next;

      delete p;

      count--;

      if(head==NULL)tail=head;

      return value;

  }

}

//-------------

int Stack::GetCount()

{

    return count;

}

//---------

void Stack::clear()

{

     node *p,*q;

     head=NULL;

     tail=NULL;

     p=head;

     while(p!=NULL)

     {

       q=p;p=q->next;

       delete q;

     }

}

//------------

void xnd()

{

     char a[50];

     Stack mst=Stack();

     cout<<"

Nhap xau ky tu: ";gets(a);

     for(int i=0;i<strlen(a);i++)

     {

       mst.Store(&a[i]);

     }

     cout<<"

Xau nghich dao la: ";

     for(int i=0;i<strlen(a);i++)

     {

        char ch;

        ch=*((char*)mst.Retrieve());

        cout<<ch;

     }

}

//-------------

void np()

{

     int n,x[20];

      int j=0;

     Stack mst=Stack();

     cout<<"

Nhap so nguyen: ";cin>>n;

     while(n>0)

     {

        x[j]=n%2;

        mst.Store(&x[j]);

        j++;

        n=n/2;

     }

     n=mst.GetCount();

     cout<<"

So nhi phan la: ";

     for(int i=0;i<n;i++)

     {

     int a;

     a=(*(int*)mst.Retrieve());

     cout<<a;

     }

}

//--------

void CTE()

{

     int b[50],c[50],i,j=0,s=0,t=0;

     srand(time(0));

      Stack st=Stack();

     cout<<"

Nhap N: ";cin>>n;

     //tao ma tran ngau nhien

while(1)

{

     for(int i=1;i<n+1;i++)

     {

        for(int j=1;j<n+1;j++)

        {

          a[i][j]=rand()%2;

        }

        a[i][i]=0;

        for(int j=1;j<n+1;j++)

        {

           s=s+a[i][j];

        }

        if(s%2!=0||s==0)i--;

        s=0;

     }

     for(int i=1;i<n+1;i++)

       for(int j=1;j<n+1;j++)

         if(a[i][j]!=a[j][i])t++;

         if(t!=0)

         {

         t=0;continue;

         }

         else break;

}

     //in ma tran

     cout<<"

Ta co ma tran la:

";

     for(int i=1;i<n+1;i++)

     {cout<<"

";

        for(int j=1;j<n+1;j++)

        cout<<a[i][j]<<" ";

        }

     cout<<"

Ta co chu trinh EULER: ";

     for(int i=1;i<n+1;i++)b[i]=i;

     st.Store(&b[1]);

      j=1;

     while(st.GetCount()!=0)

     {

        i=1;

        int s=(*(int*)st.Examine());

        while(i<n+1&&a[s][i]==0)i++;

        if(i==n+1){c[j]=(*(int*)st.Retrieve());j++;}

        else

        {

            st.Store(&b[i]);

            a[i][s]--;

            a[s][i]--;

        }

     }

     for(i=j-1;i>=1;i--)cout<<c[i]<<" ";

}

//-----------

void DEL()

{

     int n,i,j=0,b[50],c[50],s=0,t=0,dem=0;

     Stack stm=Stack();

     srand(time(0));

     cout<<"

Nhap n: ";cin>>n;

while(1)

{

        for(int i=1;i<n+1;i++)

        {

             for(int j=1;j<n+1;j++)

             a[i][j]=rand()%2;

             a[i][i]=0;

        }

        for(int i=1;i<n+1;i++)

        {

             for(int j=1;j<n+1;j++)

                s=s+a[i][j];

             if(s%2!=0)dem++;

             s=0;

             }

        for(int i=1;i<n+1;i++)

          for(int j=1;j<n+1;j++)

            if(a[i][j]!=a[j][i])t++;

            if(t!=0||dem!=2)

            {

            dem=0;

            t=0;continue;

            }

            break;

}

//in ma tran

 cout<<"

Ta co ma tran la:

";

     for(int i=1;i<n+1;i++)

     {cout<<"

";

        for(int j=1;j<n+1;j++)

        cout<<a[i][j]<<" ";

        }

     cout<<"

Ta co duong di EULER: ";

     for(int i=1;i<n+1;i++)b[i]=i;

     stm.Store(&b[1]);

     j=1;

     while(stm.GetCount()!=0)

     {

         i=1;

         int s=(*(int*)stm.Examine());

         while(i<n+1&&a[s][i]==0)i++;

         if(i==n+1)

         {

             c[j]=(*(int*)stm.Retrieve());

             j++;

         }

         else

         {

             stm.Store(&b[i]);

             a[i][s]--;

             a[s][i]--;

         }

     }

     for(int i=j-1;i>=1;i--)cout<<c[i]<<" ";

}

//----------

int main()

{

    /*xnd();

    np();*/

    //CTE();

    DEL();

    getch();

}