如何通过BFS和DFS图结构练习判断节点间可达性？

本文共计435个文字，预计阅读时间需要2分钟。

题目：图结构练习——BFS/DFS——判断可达性时间限制：1000MS内存限制：65536K

题目描述：输入包含两个整数n和m，分别代表n个节点和m条边。这些边代表n个节点之间的连通关系，即有m个通道连接这些节点。

下面m行，每行包含两个整数a，表示这两个节点之间存在一个通道。

输出：输出YES表示所有节点之间都可达，否则输出NO。

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

Time Limit: 1000MS Memory limit: 65536K

题目描述

输入

第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。

下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。

输出

示例输入

2 1 1 2 2 1 2 1

示例输出

NO YES

提示

来源

赵利强

示例程序

#include<stdio.h> #include <stdlib.h> #include<memory.h> #define MAX 1000 int map[MAX][MAX],v[MAX]; int n,m; void DFS(int x) { int i; v[x] = 1; for(i=1;i<=n;i++) { if(!v[i] && map[x][i]==1) { DFS(i); } } } int main() { int x,i,y; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { v[i] = 0; } for(i=0;i<m;i++) { scanf("%d%d",&x,&y); map[x][y] = 1; } DFS(n); if(v[1]==1) { "YES\n"); } else { "NO\n"); } memset(v,0,sizeof(v)); memset(map,0,sizeof(map)); } return 0; }