纯DFS也能过
  • 板块P1551 亲戚
  • 楼主hyh0926
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/11 18:48
  • 上次更新2024/3/11 20:41:41
查看原帖
纯DFS也能过
742030
hyh0926楼主2024/3/11 18:48
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
vector<int> v[5005];
bool f[5005];
bool dfs(int l,int s)
{
	f[l]=1;
	if(l==s)
	{
		return 1;
	}
	else
	{
		for(int i=0;i<v[l].size();i++)
		{
			if(!f[v[l][i]])
			{
				if(dfs(v[l][i],s))
				{
					return 1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=m;i++)
	{
		int m1,m2;
		cin>>m1>>m2;
		v[m1].push_back(m2);
		v[m2].push_back(m1);
	}
	for(int i=1;i<=p;i++)
	{
		int p1,p2;
		cin>>p1>>p2;
		memset(f,0,sizeof(f));
		if(dfs(p1,p2))
		{
			cout<<"Yes"<<endl;
		}
		else
		{
			cout<<"No"<<endl;
		}
	}
	return 0;
}
2024/3/11 18:48
加载中...