有向图dfs一遍即可。
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 60 #define MAXM 2010 using namespace std; int n,m,c=1,head[MAXN]; bool vis[MAXN]; struct Edge{ int next,to; }a[MAXM]; char tp[100000],*p1=tp,*p2=tp; char get_char(){ return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();} return date*w; } inline void add_edge(int x,int y){ a[c].to=y;a[c].next=head[x];head[x]=c++; } void dfs(int rt){ for(int i=head[rt],will;i;i=a[i].next){ will=a[i].to; if(!vis[will]){ vis[will]=true; dfs(will); } } } void solve(){ n=read();m=read(); for(int i=1;i<=n;i++)vis[i]=false; for(int i=1,x,y;i<=m;i++){ x=read();y=read(); add_edge(x,y); } vis[1]=true; dfs(1); if(vis[n])printf("Yes\n"); else printf("No\n"); } int main(){ solve(); return 0; }