链接：https://www.nowcoder.net/acm/contest/76/F
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：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”。
输入例子:
5 5
1 3
2 3
3 4
2 4
4 5
输出例子:
Yes
-->
示例1
输入
5 5
1 3
2 3
3 4
2 4
4 5
输出
Yes
示例2
输入
4 3
1 2
2 3
4 1
输出
No
思路：题意就是在有向图中判断指定的两点是否连通，下面放上dfs和bfs的代码：
dfs:
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
vector <int> a[1001]; //用邻接表记录，对于稀疏图，可以节省内存
int visit[1001]; //标记是否访问过
int n;
int flag; void dfs(int i){
if(visit[i]){
return ;
}
visit[i] = 1;
for(int j = 0; j < a[i].size(); j++){ //遍历当前顶点的相邻顶点
if(a[i][j] == n){ //如果他的邻居就是n直接退出，否则继续深搜的他邻居的邻居
flag = 1;
return ;
}
dfs(a[i][j]);
}
} int main(){
int m, x, y;
while(scanf("%d%d", &n, &m) == 2){
flag = 0;
memset(visit, 0, sizeof(visit));
memset(a, 0, sizeof(a));
for(int i = 0; i < m; i++){
scanf("%d%d", &x, &y);
a[x].push_back(y);
}
visit[1] = 1;;
for(int i = 0; i < a[1].size(); i++){ ////遍历当前顶点的相邻顶点
if(a[1][i] == n){
flag = 1;
break;
}
dfs(a[1][i]);
}
if(flag){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
bfs:
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
bool map[1001][1001];
bool visit[1001];
bool flag = 0;
int n;
queue <int> myq; int bfs(int i){
if(i == n){
return 1;
}
visit[i] = 1;
myq.push(i);
while(!myq.empty()){
int x = myq.front();
myq.pop();
for(int j = 1; j <= n; j++){
if(map[x][j] && visit[j] == 0){
if(j == n){
return 1;
}
visit[j] = 1;
myq.push(j);
}
}
}
return 0;
} int main(){
int m;
while(scanf("%d%d", &n, &m) == 2){
memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit));
int a, b;
for(int i = 0; i < m; i++){
scanf("%d%d", &a, &b);
map[a][b] = 1;
}
int ans = bfs(1);
if(ans == 1){
printf("Yes\n");
}
else{
printf("No\n");
}
} return 0;
}