题解 P2296 【寻找道路】

· · 题解

这道题的难点在于“路径上的所有点的出边所指向的点都直接或间接与终点连通”这句话，意思就是说一个点是合法的，当且仅当其所有子节点都与终点联通。但是，一个点是合法的，不代表他的子节点都是合法的！

理解了这句话后，可以容易的想到所有【不合法】的点是【不与终点联通的点】+【不与终点联通的点的所有子结点（哪怕该子节点与终点联通也不合法）】于是，三步解决问题。

1.反向bfs找到所有不与终点联通的点。

2.用for循环遍历所有不与终点联通的点并将其子节点也找出来(同样反向)

3.正向bfs从s->t

代码如下：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> edge[10005];//正边
vector<int> anti_edge[10005];//反边
int connect[10005];//connect[i]表示i点是否与终点联通      1联通     0不联通
int true_connect[10005];// true_connect[i]表示i点是否合法       1合法      0不合法
int visit[10005];//小优化，避免第三步的正向bfs陷入环中。没有也能过
int s,t;
struct node{
    int now;
    int d;
    node(int n1,int d1): now(n1),d(d1) {}
};
int main(){
int n,m; cin>>n>>m;
for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    if(u==v) continue;
    edge[u].push_back(v);
    anti_edge[v].push_back(u);
}
cin>>s>>t;
//从终点逆向bfs 
queue<int> q1;
q1.push(t);
while(!q1.empty()){
    int now=q1.front(); q1.pop();
    connect[now]=1;
    for(int i=0;i<anti_edge[now].size();i++){
        int to=anti_edge[now][i];
        if(connect[to]==0) q1.push(to);
    }
} 
for(int i=1;i<=n;i++) true_connect[i]=1;
for(int i=1;i<=n;i++){
    if(connect[i]==0){
        true_connect[i]=0;
        for(int j=0;j<anti_edge[i].size();j++){
            int to=anti_edge[i][j];
            true_connect[to]=0;
        }
    }     
} 
queue<node> q2;
q2.push( node(s,0) );
while(!q2.empty()){
    node n=q2.front(); q2.pop();
    int now=n.now;
    int d=n.d;
    visit[now]=1;
    if(now==t) { cout<<d; return 0;    }
    for(int i=0;i<edge[now].size();i++){
        int to=edge[now][i];
        if(true_connect[to]==1 && visit[to]==0 )    q2.push( node(to,d+1) );
    }    
}
    cout<<-1; 
    return 0;
}