LZK-7.22.判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）
【问题描述】试基于图的深度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
                    注意：算法中涉及的图的基本操作必须在此存储结构上实现。

【输入形式】

     对于如上所示的有向图，设置输入形式如下：

     5        //结点个数

     A B C D E//输入多个结点值，每个值之间用一个空格隔开

     6        //有向弧个数

     A B    //第1条边的弧尾和弧头，中间用一个空格隔开

     A C    //第2条边的弧尾和弧头，中间用一个空格隔开

     A D    //第3条边的弧尾和弧头，中间用一个空格隔开

     D E    //第4条边的弧尾和弧头，中间用一个空格隔开

     E C    //第5条边的弧尾和弧头，中间用一个空格隔开

     C B    //第6条边的弧尾和弧头，中间用一个空格隔开

     A E    //输入顶点Vi和Vj，中间用一个空格隔开

【输出形式】存在由顶点vi到顶点vj的路径则输出1，否则输出0                
【样例输入】

5
A B C D E
6
A B
A C
A D
D E
E C
C B
A E

【样例输出】 1

#include<iostream>
#include<unordered_map>
#include<vector>
#include<cstring>

using namespace std;

const int N = 100010;
int n, m;
int h[N],e[N],ne[N],idx;
bool st[N];
unordered_map<char, int> vertexMap;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

bool dfs(int s, int t){
    if(s == t) return true;
    st[s] = true;
    for(int i = h[s];i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            dfs(j, t);
            return true;
        }
    }
    return false;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n;
    string verticesStr;
    cin >> verticesStr;

    for(int i = 0;i < n;i ++){
        vertexMap[verticesStr[i]] = i;
    }

    cin >> m;
    char sChar,eChar;
    for(int i = 0;i < m;i ++){
        cin >> sChar >> eChar;
        int a = vertexMap[sChar];
        int b = vertexMap[eChar];
        add(a, b);
    }

    cin >> sChar >> eChar;
    int s = vertexMap[sChar];
    int t = vertexMap[eChar];
    if(dfs(s, t)) cout << 1 << endl;
    else cout << 0 << endl;


    return 0;
}