【不一样的题解】寻找道路

思路：

先将整个有向图用集合数组存储，
再通过深搜检查哪些节点可以到达终点，
最后从起点开始广搜，找到一条符合要求的能够通往终点的最短路。

---

代码：

#include<iostream>
#include<set>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+15;
int n,m,a,b,sp,ep,c,r=2147483647;
set<int> s[N];//这里不开二维数组是因为开二维数组会爆空间，开集合无论如何都比二维数组节省一些空间，所以采用集合
bool vis[N],arr[N];//vis=visited,arr=arrived
bool dfs(int t){//深搜找到能够到达终点的位置并标记
    if(t==ep){//已经到达
        arr[t]=1;
        return 1;
    }
    if(s[t].empty()){//不可能到达
        arr[t]=0;
        return 0;
    }
    for(auto it=s[t].begin();it!=s[t].end();it++){//遍历集合，it指针变量类型为set<int>::iterater，用auto简单代替
        if(!vis[*it]){//判断是否未走过
            vis[*it]=1;//先标记
            if(arr[*it])arr[t]=1;//已经搜索过判断为走过可以避免重复搜索
            else{//未搜索到结果为可以走
                int k=dfs(*it);//类似于记忆化搜索
                if(!arr[*it])arr[*it]=k;//标记
                if(arr[*it])arr[t]=1;
//因为这是当前节点的延伸节点，既然延伸节点可以到达，就说明当前节点一定可以到达，所以标记完对当前节点也要进行标记
            }
            vis[*it]=0;//最后撤销标记
        }
    }
}
struct node{//自定义结构体
    int num,steps;
};
queue<node>q;//结构体队列
void bfs(){//广搜找到最短路
    q.push({sp,0});
    vis[sp]=1;
    while(q.size()){
        node f=q.front();//取出队首
        q.pop();//删除队首
        if(f.num==ep)r=min(r,f.steps);//到达后更新r的值（最少步数）
        else{//未到达
            bool flag=1;
            for(auto it=s[f.num].begin();it!=s[f.num].end();it++){
                if(!vis[*it])flag=flag&arr[*it];//利用布尔类型变量值的特点对其进行逻辑“与”运算
                if(!flag)break;
            }
            if(flag){//说明该节点所有延伸节点都可以到达终点
                for(auto it=s[f.num].begin();it!=s[f.num].end();it++){//遍历集合的操作
                    if(!vis[*it]){//判断是否未途径这里，实际上用到了贪心的思想，绕远路会没有走近路到得早
                        vis[*it]=1;//对此标记
                        q.push({*it,f.steps+1});//加入队列
                    }
                }
            }
        }
    }
}
int main(){
    //数据的读入
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        s[a].insert(b);
    }
    //开始深搜判断节点可否到达，从起点开始即可
    cin>>sp>>ep;
    dfs(sp);
    //开始广搜找到最短路长度
    memset(vis,0,sizeof(vis));
    bfs();
    //算法的输出
    cout<<(r==2147483647?-1:r)<<endl;
    return 0;
}