时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
从实验室出来后，你忽然发现你居然把自己的电脑落在了实验室里，但是实验室的老师已经把大门锁上了。更糟的是，你没有那个老师的电话号码。你开始给你知道的所有人打电话，询问他们有没有老师的电话，如果没有，他们也会问自己的同学来询问电话号码。那么，你能联系到老师并且拿到电脑吗。
输入描述:
存在多组测试样例
每组样例的第一行分别是两个整数n(1<n<=50)，m(1<m<=2000)，n是在题目当中出现的人数，其中你的序号是1号，实验室老师的序号是n。
接下来的m行，每行有两个整数x(1<=x<=n)，y(1<=y<=n)，代表x有y的电话号码。
输出描述:
对于每组测试样例，如果你最终能联系到老师，输出“Yes”，否则输出“No”。
思路一：
由于题目中电话号单向拥有，所以只能建单向边，直接从1开始深搜（广搜亦可），判断是否到N即可。
代码：
#include<bits/stdc++.h>
using namespace std;
bool a[51][51];
int n;
void dfs(int x)
{
if(a[x][n] == true){
puts("Yes");
exit(0);
}
for(int i = 1; i < n; ++i) {
if(a[x][i] == true){
dfs(i);
}
}
return ;
}
int main()
{
int m, i, j, x, y;
ios::sync_with_stdio(false);
cin >> n >> m;
for(i = 0; i < m; ++i){
cin >> x >> y;
a[x][y] = true;
}
dfs(1);
puts("No");
return 0;
}
思路二：
floyd算法判断传递闭包即可
代码：
#include<bits/stdc++.h>
using namespace std;
int n,flag;
int ma[55][55];
int main(){
int m;
while(~scanf("%d %d",&n,&m)){
memset(ma,0,sizeof(ma));
while(m--){
int x,y;
cin>>x>>y;
ma[x][y] = 1;
}
for(int k = 1 ; k <= n ; k ++){
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= n ; j++){
if(ma[i][k]&&ma[k][j])ma[i][j] = 1;
}
}
}
ma[1][n]?puts("Yes"):puts("No");
}
}
思路三：
定义标记数组把每一个与1连通的点赋值为1，最后判断n点是否为1
代码：
#include <iostream>
using namespace std;
int main()
{
int n,m,a,b,i,p[51]={0};
p[1]=1;
cin>>n>>m;
for(i=0;i<m;i++)
{
cin>>a>>b;
if(p[a]==1)
p[b]=1;
}
if(p[n]==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}
