题目中的点可以分为三种:
① 自己指向的节点都可以到达终点。
② 自己可以到达终点的点。
③ 普通的点。
如果一个点可以到达终点且这个点可到达的点可到达终点,那么这个点满足题意,建反向边从终点先遍历一次确定2号点,再从起点遍历一次并用chec函数判断1类型点,两次bfs遍历O(n+m)的复杂度。
(vector开为局部变量中传参会超时)
# include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=10100,M=200100;
int d[N];
vector<bool>st(N);
vector<vector<PII>>g(M),reg(M);
inline void check(int u)
{
queue<int>q;
q.push(u);
while(q.size())
{
int t=q.front();
q.pop();
for(auto k:reg[t])
{
if(!st[k.x])
{
st[k.x]=1;
q.push(k.x);
}
}
}
}
inline bool chec(int x)
{
for(auto t:g[x])
{
if(!st[t.x])
return 0;
}
return 1;
}
inline void bfs(int u)
{
queue<int>q;
q.push(u);
d[u]=0;
while(q.size())
{
int t1=q.front();
q.pop();
if(!chec(t1))
continue;
for(auto k:g[t1])
{
if(d[k.x]==1e8)
{
q.push(k.x);
//cout<<k.x<<endl;
d[k.x]=d[t1]+k.y;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
while (m -- )
{
int x,y;
cin>>x>>y;
if(x!=y)
{
g[x].push_back({y,1});
reg[y].push_back({x,1});
}
}
int s,t;
cin>>s>>t;
st[t]=1;
check(t);
for(int i=1;i<=n;i++)
d[i]=1e8;
bfs(s);
if(d[t]!=1e8)
cout<<d[t];
else cout<<-1;
}