#include<stdio.h>
#include<stdlib.h>
#define m 20                      /*預定義圖的最大頂點數*/
typedef char datatype;       /*頂點信息數據類型*/
typedef struct node{           /*邊表結點*/
    int adjvex;                      /*鄰接點*/
    struct node *next;
}edgenode;
typedef struct vnode{        /*頭結點類型*/
   datatype vertex;             /*頂點信息*/
   edgenode *firstedge;     /*鄰接鏈表頭指針*/
}vertexnode;
typedef struct{                       /*鄰接表類型*/
     vertexnode adjlist [m];     /*存放頭結點的順序表*/
     int n,e;                             /*圖的頂點數與邊數*/
}adjgraph;

void createadjgraph(adjgraph *g)
    { int i,j,k;
      edgenode *s;
      printf("Please input n and e:\n");
      scanf("%d%d",&g->n,&g->e);     /*輸入頂點數與邊數*/
      getchar();
      printf("Please input %d vertex:",g->n);
for(i=0;i<g->n;i++)
      {scanf("%c",&g->adjlist[i].vertex);      /*讀入頂點信息*/
        g->adjlist[i].firstedge=NULL;            /*邊表置為空表*/
        }
      printf("Please input %d edges:",g->e);
      for(k=0;k<g->e;k++)                 /*循環e次建立邊表*/
        {   scanf("%d%d",&i,&j);         /*輸入無序對（i,j）*/
         s=(edgenode *)malloc(sizeof(edgenode));
             s->adjvex=j;                      /*鄰接點序號為j*/
         s->next=g->adjlist[i].firstedge;
         g->adjlist[i].firstedge=s;    /*將新結點*s插入頂點vi的邊表頭部*/
         s=(edgenode *)malloc(sizeof(edgenode));
             s->adjvex=i;                    /*鄰接點序號為i*/
         s->next=g->adjlist[j].firstedge;
         g->adjlist[j].firstedge=s;      
             /*將新結點*s插入頂點vj的邊表頭部*/
        }
   }

int visited[m];
void dfs(adjgraph g,int i)
{  /*以vi為出發點深度優先遍歷頂點vi所在的連通分量*/
  edgenode *p;
  printf("visit vertex: %c \n",g.adjlist[i].vertex);    /*訪問頂點i*/
  visited[i]=1;
  p=g.adjlist[i].firstedge;
  while (p)               /*從p的鄰接點出發進行深度優先搜索*/
    {  if (!visited[p->adjvex])    
                 dfs(g,p->adjvex);     /*遞歸*/
       p=p->next;
    }
}
void dfstraverse(adjgraph g)
{ /* 深度優先遍歷圖g */
 int i;
   for (i=0;i<g.n;i++)
       visited[i]=0;         /*初始化標志數組*/
   for (i=0;i<g.n;i++)
       if (!visited[i])        /*vi未訪問過*/
               dfs(g,i);
 }
 void printadjgraph(adjgraph g)
{
    int i;
    for(i=0;i< g.n;i++)
    {
        printf("%c",g.adjlist[i].vertex);
        while(g.adjlist[i].firstedge)
        {
            printf("--->%d",g.adjlist[i].firstedge->adjvex);
            g.adjlist[i].firstedge=(g.adjlist[i].firstedge)->next;
        }
        printf("\n");
    }
}

void main()
{
    adjgraph g;
    createadjgraph(&g);
    printadjgraph(g);
}