关于有向图
  • 板块题目总版
  • 楼主人间温柔
  • 当前回复33
  • 已保存回复33
  • 发布时间2020/7/16 12:51
  • 上次更新2023/11/6 23:02:14
查看原帖
关于有向图
178195
人间温柔楼主2020/7/16 12:51

最近在弄图论,有一个问题搞不定。

有一个nn个点,mm条边的有向图,判断能否从aa走到bb。 输入n,m,a,bn,m,a,b,接下来mm行,2个数x,yx,y表示从xxyy有边。结果输出YES或NO。

题目大概就是这样。YES的情况好弄,已经写好了。

求大佬,NO的情况咋弄啊???qwqqwq

代码:

#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;
}
2020/7/16 12:51
加载中...