最近在弄图论,有一个问题搞不定。
有一个n个点,m条边的有向图,判断能否从a走到b。 输入n,m,a,b,接下来m行,2个数x,y表示从x到y有边。结果输出YES或NO。
题目大概就是这样。YES的情况好弄,已经写好了。
求大佬,NO的情况咋弄啊???qwq
代码:
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#define MAXN 200005
using namespace std;
int n,m,a,b;
vector<int>v[MAXN];//存图,v[i]表示所有v能直接到的点
bool flag=false,vis[MAXN];
void dfs(int x)
{
bool f=false;
if(x==b)
{
flag=true;
return;
}
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i]])
{
vis[v[x][i]]=true;
dfs(v[x][i]);
}
vis[v[x][i]]=false;
}
}
int main()
{
cin>>n>>m>>a>>b;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
}
dfs(1);
if(flag) cout<<"Yes";
else cout<<"No";
return 0;
}