bfs、图

题意：

在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。
注意：图G中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。
输入描述:
第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
输出描述:
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。

备注
对于30%的数据，0< n≤10，0< m≤20；
对于60%的数据，0< n≤100，0< m≤2000；
对于100%的数据，0< n≤10,000，0< m≤200,000，0< x,y,s,t≤n，x≠t。

分析：

如果没有1的约束条件、那么这题也不过是在图中求最短路径的问题！而且，又因为是无权图所以只要bfs一下就可以搜索出来了！！
但是很遗憾，他有约束条件。
我们不难看出，条件一目的是排除一些点。也就是不满足条件一的点不能走。

那关键就是在于如何找到不满足条件一的点！！！
其实很简单
条件一：路径上的所有点的出边所指向的点都直接或间接与终点连通。
也就是说对于点node0，他的子节点node1,node2,node3,node4,node5...
全部都可以到达end(目标节点)
那我们怎么办呢？
先找出所有可以到达end的点，对他们进行标记。再对每个节点node0进行遍历，看它的子节点，如果有一个子节点未被标记，那么被遍历的该节点node0失格。
很简单的思路！(其实这里我们只需遍历可以到达end的点即被标记的点就可以了)
如何找到，所有可以到达end的点呢？
在记录边时反向记一份，再以end为起点进行一次搜索，找到所有能抵达的点，对他们进行标记。(因为图中有环，所以这里我们也是选择使用bfs)

代码如下、注意细节

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const int max_n = 50000;
const int max_m = 500000;
const int INF = max_m;
vector<int> G[max_n];
vector<int> T[max_n];
bool vis[max_n];
int ans[max_n];
int n, m;
int s, t;

int bfs(int st,int type) {
    if (type == 0) {
        deque<int> que;que.push_back(st);
        while (!que.empty()) {
            int cur = que.front();que.pop_front();
            if (vis[cur])continue;
            vis[cur] = true;
            for (int i = 0;i < T[cur].size();i++) {
                if (!vis[T[cur][i]])que.push_back(T[cur][i]);
            }
        }
        return -1;
    }
    fill(ans, ans + n + 1, INF);ans[st] = 0;
    deque<int> que;que.push_back(st);
    while (!que.empty()) {
        int cur = que.front();que.pop_front();
        if (!vis[cur])continue;
        if (cur == t)return ans[t];
        for (int i = 0;i < G[cur].size();i++) {
            int node = G[cur][i];
            if (!vis[node])continue;
            if (ans[node] != INF )continue;
            ans[node] = ans[cur] + 1;
            que.push_back(node);
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;int x, y;
    for (int i = 0;i < m;i++) {
        cin >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }cin >> s >> t;
    bfs(t, 0);vector<int>tmp;
    for (int i = 1;i <= n;i++) {
        if (!vis[i])continue;
        for (int j = 0;j < G[i].size();j++) {
            if (!vis[G[i][j]]) {
                tmp.push_back(i);
                break;
            }
        }
    }
    while (!tmp.empty()) {
        vis[tmp.back()] = false;
        tmp.pop_back();
    }
    cout << bfs(s,2) << endl;
}