首页 > 代码库 > SDUT OJ 2138 图结构练习——BFSDFS——判断可达性

SDUT OJ 2138 图结构练习——BFSDFS——判断可达性

技术分享
#include<iostream>
#include<memory.h>
using namespace std;
int visit[1001];
int t[1001][1001];
int k;
int n;
void dfs(int x,int n)
{
	int i;
	visit[x]=1;
	if(x==1)  
	{
		k++;
		return ;
	}
	for(i=1;i<=n;i++)
	{
		if(t[x][i]==1 && visit[i]==0)
			dfs(i,n);
	}
    return ;
}
int main()
{
    int m,a,b,i,j;
    while(cin>>n>>m)
	{
		k=0;
		memset(t,0,sizeof(t));
		memset(visit,0,sizeof(visit));
		for(i=1;i<=m;i++)
		{
			cin>>a>>b;
            t[a][b]=1;
		}
		dfs(n,n);
		if(k==1)
			cout<<"YES"<<endl;
		if(k==0)
			cout<<"NO"<<endl;
	}
	return 0;		
}

SDUT OJ 2138 图结构练习——BFSDFS——判断可达性