做旅游网站的产品经理如何,定制网站系统开发,ip138域名查询,怎么做下载类的网站某城市有n个景点#xff0c;部分景点之间有巴士免费来回接送。(1) 给定某个景点x#xff0c;如果从这个景点出发坐一次免费巴士#xff0c;可以到达多少个不同的景点#xff1f;(2) 判断景点a是否可以通过免费巴士#xff08;可换乘#xff09;到达景点b#xff1b;(3) …某城市有n个景点部分景点之间有巴士免费来回接送。(1) 给定某个景点x如果从这个景点出发坐一次免费巴士可以到达多少个不同的景点(2) 判断景点a是否可以通过免费巴士可换乘到达景点b(3) 判断全部景点之间是否都可以通过免费巴士可换乘到达。
输入格式:
第一行是n, m值分别代表景点数量免费巴士线路的数量1n,m100; 接下来有m行每行有两个整数分别代表第i(1im)条免费巴士线路连接的两个景点编号 接下来一行是景点x的编号 最后一行是景点a, b 的编号(a!b)。 说明所有景点编号都在[1, n]范围内。
输出格式:
输出有三行 第一行输出问题1的值 第二行输出问题2的判断结果YES 或者 NO; 第三行输出问题3的判断结果YES 或者 NO.
输入样例:
在这里给出一组输入。例如
5 4
1 3
1 2
4 5
1 4
1
1 5输出样例:
在这里给出相应的输出。例如
3
YES
YES注意点
1、设置vis[ ]数组记录顶点是否被访问过
2、处理完问题二后要重置vis[ ]数组
3、如果想vis[ ]顶点下标代表被访问顶点名称则for循环范围是1~n
#includeiostream
using namespace std;
const int Max 100;
int n,m;
int a[Max][Max]{0};
int vis[Max]{0};
bool search(int start,int end){ //判断两点是否有路径连通if(startend) return true;vis[start]1;for(int i1;in;i){if(a[start][i]1vis[i]0){if(search(i,end)) return true;}}return false;
}
void DFS(int start) //从某一顶点进行深度搜索
{for(int i1; in; i){if(!vis[i]a[start][i]){vis[i]1;DFS(i);}}
}int main(){cinnm;for(int i0;im;i){int a1,a2;cina1a2;a[a1][a2]a[a2][a1]1;}int x;cinx;int sum0;for(int i1;in;i){if(a[x][i]1) sum;}coutsumendl; // 问题1int start,end;cinstartend;bool resultsearch(start,end);cout(result?YES:NO)endl;//问题2for(int i1;in;i){ //重置vis数组vis[i]0;}int cnt0;for(int i1; in; i) //判断图是否连通{if(vis[i]0){DFS(i);cnt;}} //问题3cout ((cnt1)?YES : NO) endl;
}
