//Tao Class cua Queue

#include<conio.h>

#include<stdio.h>

#include<math.h>

#include<iostream.h>

int n,a[50][50];

//---------

class queue

{

      protected:

                struct node

                {

                  void *dataptr;

                  node*next;

                };

          node *head;

          node *tail;

          int count;

      public:

             void copy(const queue &q);

             void ErrorHandler();

             queue();

             queue(const queue &q);

             void operator=(const queue &q);

             virtual int Store(void*item);

             virtual void* Examine();

             virtual void *Retrieve();

             int GetCount();

             virtual void clear();

};

//--------

void queue::ErrorHandler()

{

     cout<<"

Loi: do cap phat bo nho!";

}

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

void queue::copy(const queue &q)

{

     head=NULL;tail=NULL;

     node *temp;

     temp=q.head;

     while(temp!=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=temp->dataptr;

        tail->next=NULL;

        temp=temp->next;

     }

}

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

queue::queue(){

               count = 0;

               head = NULL;

               tail = NULL;

               }

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

queue::queue(const queue &q)

{count =q.count;

     copy(q);

}

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

void queue::operator=(const queue &q)

{

     count =q.count;

     copy(q);

}

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

int queue::Store(void*item)

{

    node*p;

    p=new node;

    if(p==NULL)return 1;

    p->dataptr=item;

    p->next=NULL;

    if(count==0)

    {

       head=p;

       tail=p;

    }

    else

    {

        tail->next=p;

        tail=p;

    }

    count++;

    return 0;

}

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

void *queue::Examine()

{

   if(count==0)return NULL;

   else{return head->dataptr;}   

}

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

void *queue::Retrieve()

{

     node *p;

     void*value;

     p=new node;

     value=head->dataptr;

     p=head;

     head=p->next;

     delete p;

     count--;

     if(head==NULL)tail=NULL;

     return value;

}

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

int queue::GetCount()

{return count;}

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

void queue::clear()

{

     node*p,*q;

     p=new node;

     q=new node;

     head=NULL;

     tail=NULL;

     p=head;

     while(p!=NULL)

     {

     q=p;

     p=q->next;

     delete q;

     }

}

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

void BFS()

{

     int b[50],cx[50],i;

      cout<<"

Nhap N: ";cin>>n;

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

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

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

       a[i][i]=0;

       }

     cout<<"

Ta co  ma tran:

";

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

     {cout<<"

";

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

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

     }

     cout<<"

BFS: ";

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

           {cx[i]=1;}

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

          if( cx[t] == 1 ){ 

              queue mq = queue();

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

              mq.Store(&b[t]);

              cx[t] = 0;

              while( mq.GetCount() != 0 ){

                     int u = *((int*) mq.Retrieve());

                     cout <<" "<<u;

                     for( int w = 1 ; w < 6 ; w++ )

                          if( a[u][w] != 0 && cx[w] == 1 ){

                              mq.Store(&b[w]);

                              cx[w] = 0; 

                              }

}

}

}

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

void NN()

{

     int n,u,v,b[50],cx[50],p[50],t=1,i;

     queue mq=queue();

     cout<<"

Nhap N: ";cin>>n;

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

     {p[i]=0;cx[i]=1;}

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

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

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

       a[i][i]=0;

       }

     cout<<"

Ta co  ma tran:

";

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

     {cout<<"

";

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

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

     }

     cout<<"

Tu dinh: ";cin>>u;

     cout<<"

Den dinh: ";cin>>v;

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

        mq.Store(&b[u]);

        cx[u]=0;

          while(mq.GetCount()!=0)

          {

           int x=(*(int*)mq.Retrieve());

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

             if(a[x][w]!=0&&cx[w]==1)

             {

             mq.Store(&b[w]);

             p[w]=x;

             cx[w]=0;

       }

     }

     while(v!=u&&p[v]!=0)

     {

        b[t]=v;

        t++;

        v=p[v];

     }

     if(v!=u){cout<<"

Ko co dg di giua "<<u<<" va "<<v;}

     else

     {

         b[t]=u;

         t++;

         cout<<"

Dg di giua u va v la: ";

         for(int i=t-1;i>=1;i--){cout<<b[i]<<" ";}

         }

}

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

int main()

{

   // BFS();

    NN();

    getch();

    }