#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;

char vertex[20];   //深搜用栈，广搜用队列

typedef struct enode {   //表结点
    int nexttov;           //相邻顶点
    struct enode * nextedge; //相邻下一个表结点
}enode;

typedef struct {   //头结点
    char vertex;      //顶点信息
    enode *firstedge;   //第一条边（出度）/第一个表结点
}vnode;

typedef struct {   //图
    int vnum,edgenum;
    vnode vnodestr[20];   //头结点信息数组
}graph;

void creategraph(graph *g)
{
    int i,from,to;
    enode *p,*pedge;
    printf("输入有向图顶点个数\n");
    scanf("%d",&g->vnum);
    getchar();
    printf("输入有向图顶点名字\n");
    for(i=0;i<g->vnum;i++)
    {
        scanf("%c",&g->vnodestr[i].vertex);
        g->vnodestr[i].firstedge = NULL;   //顶点的第一个表结点初始化空
    }

    printf("输入有向图边个数\n");
    scanf("%d",&g->edgenum);
    printf("输入有向图边信息\n");
    printf("起点   终点\n");
    for(i=0;i<g->edgenum;i++)
    {
        scanf("%d%d",&from,&to);
        pedge = (enode*)malloc(sizeof(enode));   //开空间给表结点
        pedge->nextedge = NULL;
        pedge->nexttov = to;

        p = g->vnodestr[from].firstedge;
        if(!p)
        {
             g->vnodestr[from].firstedge = pedge;
        }
        else   //尾插
        {
         while(p->nextedge)
            {
                p = p->nextedge;
            }
            p->nextedge = pedge;
        }
    }
}

int findvsite(graph *g,char v)
{
    int i;
    for(i=0;i<g->vnum;i++)
    {
        if(g->vnodestr[i].vertex==v)   //返回顶点位序
            return i;
    }
    return -1;
}

int getarcsnum(graph *g,int index)
{
    int k = 0;
    enode *p = g->vnodestr[index].firstedge;
    if(index>=0&&index<g->vnum)
    {
        while(p)
        {
            k++;   //有一个邻接点就是有一个出度
            p = p->nextedge;
        }
        return k;
    }
    return -1;
}

int connected(graph *g,int from,int to)   //看有没边
{
    enode *p = g->vnodestr[from].firstedge;
    if((from<0||from>=g->vnum) || (to<0&&to>=g->vnum))
     return 0;
    while(p)
    {
        if(p->nexttov==to)
            return 1;     //有邻接点就是有边
        p = p->nextedge;
    }
    return 0;
}

/*void dfssearch0(graph *g)     //非递归实现深搜
{
    int i,top = 0,k,m;
    int flag[20];     //记录顶点的下标
    enode *p;
    for(i=0;i<20;i++)
        flag[i] = -1;   //从第一个顶点开始
    vertex[top++] = g->vnodestr[0].vertex;
    flag[0] = 0;
    while(top>0&&top<g->vnum){
        if(!p)       //退栈，从上一个顶点开始
          i=flag[--m];
        else m = i = flag[top-1];
        p = g->vnodestr[i].firstedge;
        while(p)
        {
            for(k=0;k<top;k++)
                if(flag[k]==p->nexttov)
                    break;
            if(k==top)
                {
                vertex[top] = g->vnode[p->nexttov].vertex;
                flag[top++] = p->nexttov;
                break;
            }
                p = p->nextedge;
        }
    }
}*/

int visited1[20];
int visited2[20];

void dfs(graph g,int i)
{
    enode *p;
    printf("访问节点%c\n",g.vnodestr[i].vertex);
    visited1[i] = 1;   //访问了就标记1，不能再访问了
    p = g.vnodestr[i].firstedge;
    while(p)
    {
        if(!visited1[p->nexttov])
        {
            dfs(g,p->nexttov);
        }
        p = p->nextedge;
    }
}

void dfssearch(graph g)
{
    int i,j;
    for(i=0;i<g.vnum;i++)
    {
        visited1[i] = 0;
    }
    for(j=0;j<g.vnum;j++)
    {
        if(!visited1[j])
        {
            dfs(g,j);
        }
    }
}

void bfssearch(graph g)
{
    queue<int> q;
    enode *p;
    int i,j,w;
    for(i=0;i<g.vnum;i++)
    {
        visited2[i] = 0;
    }
    for(j=0;j<g.vnum;j++)
    {
        if(!visited2[j])
            q.push(j);   //没访问过就入队
        while(!q.empty())
        {
            w = q.front();   //队头元素要先被访问
            printf("%c ->",g.vnodestr[w].vertex);
            visited2[w] = 1;   //访问完了就标记1，不能再访问了
            q.pop();   //访问完了就出队给下一个元素
            for(p=g.vnodestr[w].firstedge;p;p=p->nextedge)   //找访问的元素的邻接点入队待访问
            {
                if(!visited2[p->nexttov])
                    q.push(p->nexttov);
            }
        }
    }
}

int main()
{
    graph g;
    creategraph(&g);

    printf("%d\n",findvsite(&g,'b'));
    printf("%d\n",getarcsnum(&g,1));
    printf("%d\n",connected(&g,1,3));

    printf("深搜-----\n");
    dfssearch(g);

    printf("广搜-----\n");
    bfssearch(g);

    printf("\n");
    return 0;
}