WD-7.27. 判别是否存在简单路径。
【问题描述】采用邻接表存储结构，编写一个判别有向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。顶点的数据类型为整型。
【输入形式】

<顶点数><空格><弧数><回车>

<输入顶点值序列，以空格分隔><回车>

<依次输入各条弧信息，弧头弧尾用空格分隔，每输入一组回车结束>

<顶点1><逗号><顶点2><逗号><长度k>

【输出形式】<Exist the path!|Not exist the path!>

【样例输入】对于有3个顶点（分别是1,2,3），2条弧（1->3,1->2）的有向图，判断顶点1到顶点3之间是否存在长度为1的简单路径。具体输入如下。

3 2
1 2 3
1 3
1 2
1,3,1

【样例输出】

Exist the path!

#include<iostream>
#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];

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

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

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

    for(int i = 0;i < m;i ++){
        int a,b;
        cin >> a >> b;
        add(a, b);
    }

    int a,b,k;
    cin >> a >> b >> k;

    if(dfs(a,b,1,k)) cout << "Exist the path!" << endl;
    else cout << "Not exist the path!" << endl;

    return 0;
}