首页 > 代码库 > sdut oj 3058 路线冲突问题（BFS+记录路径算法，回溯路径 ）
sdut oj 3058 路线冲突问题（BFS+记录路径算法，回溯路径 ）
路线冲突问题
题目描述
给出一张地图，地图上有n个点，任意两点之间有且仅有一条路。点的编号从1到n。
现在兵团A要从s1到e1，兵团B要从s2到e2，问两条路线是否会有交点，若有则输出交点个数，否出输出”success”。
输入
多组输入。
对于每组输入。
第一行输入n（1 <= n <= 100000），代表点的个数。
接下来的n-1行，每行包含两个整数u,v(1 <= u,v <= n)，代表u，v之间有一条相连。
再接下里的一行包含四个整数s1,e1,s2,e2（1 <= s1,e1,s2,e2 <= n）。
输出
问两条路线是否会有交点，若有则输出交点个数，否出输出”success”。
示例输入
31 22 31 2 2 3
示例输出
1
算法分析：两次bfs记录下起点到终点的路径就行了，然后比较两条路径有没有重合点。
代码：
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <vector>#include <queue>#include <algorithm>using namespace std;vector<int>q[100002];bool vis[100002];int fa[100002];bool path[100002];void BFS(int s, int e){ memset(vis, false, sizeof(vis)); memset(fa, 0, sizeof(fa)); vis[s]=true; queue<int>p; int i, j, len; while(!p.empty()) p.pop(); p.push(s); int flag=0; while(!p.empty()) { int dd=p.front(); p.pop(); len=q[dd].size(); for(i=0; i<len; i++) { if( vis[q[dd][i]]==false ) { fa[ q[dd][i] ] = dd; //记录前驱 //printf("%d--%d\n", dd, fa[q[dd][i]] ); if(q[dd][i]==e) //找到终点跳出 { flag=1; break; } p.push( q[dd][i] ); vis[ q[dd][i] ] =true; } } if(flag==1) break; }}int main(){ int n; int i, j; int u, v; int a, b, x, y; while(scanf("%d", &n)!=EOF) { for(i=0; i<=n; i++) q[i].clear(); for(i=0; i<n-1; i++) { scanf("%d %d", &u, &v); q[u].push_back(v); q[v].push_back(u); } scanf("%d %d %d %d", &a, &b, &x, &y); BFS(a, b);//fa数组弹出 memset(path, false, sizeof(path)); for(i=fa[b]; i!=0; i=fa[i] ) { path[i]=true; } path[b]=true; BFS(x, y); int cnt=0; for(j=fa[y]; j!=0; j=fa[j] ) { if(path[j]==true) cnt++; } if(path[y]==true) cnt++; if(cnt==0) printf("success\n"); else printf("%d\n", cnt); } return 0;}
sdut oj 3058 路线冲突问题（BFS+记录路径算法，回溯路径 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。