/*有向圖的鄰接表的相關算法
  時間:2008.09.10
  版本:v2.0
*/
#include   <iostream.h>
#include   <stdlib.h>
typedef  int  VertexType ;          //頂點數(shù)據(jù)類型
#define   MAX_VERTEX_NUM   20         //最大頂點數(shù)
#define   MAX_EDGE_NUM   40          //最大邊數(shù)
int   visited[MAX_VERTEX_NUM];       //訪問標志數(shù)組
/*結點類型*/
struct   ArcNode
{
   int   adjvex;           //該弧所在的頂點位置
   ArcNode   *nextarc;       //指向下一條弧
};
/* 表頭結點定義*/
struct   VNode
{
   VertexType   data;           //頂點信息
   ArcNode   *firstarc;         //指向第一條弧
};
typedef VNode AdjList[MAX_VERTEX_NUM];
/*圖定義*/
struct ALGraph
{
    AdjList  vertices;
    int   vexnum,arcnum;
};
ALGraph  G;
void   CreateDG(ALGraph   &G)
{
  int   i,j,k;
  ArcNode   *p;
  cout<<"創(chuàng)建一個有向圖:"<<endl;//也就是依次輸入N個選手的勝負情況
  cout<<"頂點數(shù):"<<endl;   cin>>G.vexnum;     //選手數(shù)N
  cout<<"邊數(shù):"<<endl;     cin>>G.arcnum;   //選手比賽次數(shù),由于是單循環(huán)肯定是N*(N-1)*/2盤比賽
  /*        初始化        */
  for(i=1;i<=G.vexnum;i++)
  {
     G.vertices[i].data=i;
     G.vertices[i].firstarc=NULL;
  }
  for(k=0;k<G.arcnum;k++)
  {
     cout<<"請輸入第"<<k+1<<"條邊:";
     cin>>i>>j;
     p=new ArcNode;
     p->adjvex=j;
     p->nextarc=G.vertices[i].firstarc;
     G.vertices[i].firstarc=p;
   }
}
void   Disp(ALGraph G)
{
   int   i;
   ArcNode   *p;
   cout<<"輸出圖為:"<<endl;
   for(i=1;i<=G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p!=NULL)
     {
         cout<<"("<<i<<","<<p->adjvex<<")";
         p=p->nextarc;
     }
    cout<<endl;
   }
   cout<<"*******************************"<<endl;
}
int  dfs(int v)   //深度優(yōu)先遍歷
{
  int count=0;
  ArcNode *p=new ArcNode;
    cout<<G.vertices[v].data<<"＊＊＊";
  count++;
  visited[v]=1;
  p=G.vertices[v].firstarc;
  while(p!=NULL)
  {
    if(!visited[p->adjvex])

    count=dfs(p->adjvex)+1;
    p=p->nextarc;
   }
 return count;
}
int   main()
{
  int visited[20];
  int v;
  int count;
  char flag;//是否繼續(xù)搜索
  bool isshow=true;//判斷是否滿足要求
  CreateDG(G);
  Disp(G);

      for(int i=1;i<G.vexnum;i++)
      {visited[i]=0;}
     for(int v=1;v<G.vexnum;v++)
     {
        if( dfs(v)==G.vexnum)
        {
           cout<<endl;
           cout<<"這條滿足要求";
           break;
        }
        cout<<endl;
     }
  cout<<"程序結束!"<<endl;
}


 /* for(;;)//只要深度遍歷能把所儲存的頂點都依次輸出就得到了要求的序列,當然根據(jù)情況有可能不只一條
  {
      for(int i=1;i<G.vexnum;i++)
      {visited[i]=0;}
     cout<<"請輸入深度優(yōu)先搜索的頂點:";
     cin>>v;cout<<endl;
     cout<<"深度優(yōu)先序列:";
     //if(isshow=dfs(v))
    // {
        cout<<dfs(v);
        cout<<endl;
       // cout<<"該序列滿足要求!"<<endl;
    // }
     //else
     //{
        cout<<endl;
        //cout<<"該序列不滿足要求!"<<endl;
     //}
     cout<<endl;
     cout<<"是否結束搜索?(Y/N)"<<endl;
     cin>>flag;
     if(flag=='Y')
     {
        break;
     }
  }  */