本文主要是介绍SDUTOJ 3058 路线冲突问题 ——bfs记录路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
路线冲突问题
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
给出一张地图，地图上有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”。
示例输入
3
1 2
2 3
1 2 2 3
示例输出
1
提示
来源
zmx
#include <stdio.h>
#include <string.h>
#include <queue>using namespace std;struct node
{int v;int next;
}ls[200010];//邻接表存储输入int head[100010];//邻接表的头
bool vis[100010];//bfs的标记数组
int pre[100010];//记录路径的数组
bool hs[100010];//判断重复路径的哈希表
int num,sum;queue <int> q;//bfs的队列void creat(int x,int y)
{ls[num].v = y;ls[num].next = head[x];head[x] = num++;
}//建立邻接表void bfs(int s,int e)
{int t;memset(vis,false,sizeof(vis));while(!q.empty())q.pop();q.push(s);vis[s] = true;while(!q.empty()){t = q.front();q.pop();for(int i = head[t];~i;i = ls[i].next){int v = ls[i].v;if(!vis[v]){pre[v] = t;//记录v的前驱节点是t,v是当前搜到的点，是和t相连的下一个节点，那么v的前一个节点就是tif(pre[e])return ;//找到e后就立刻跳出q.push(v);vis[v] = true;}}}
}int main()
{int n,x,y,s1,e1,s2,e2;while(~scanf("%d",&n)){num = 0;sum = 0;memset(head,-1,sizeof(head));memset(hs,false,sizeof(hs));for(int i = 0;i < n - 1;i++){scanf("%d%d",&x,&y);creat(x,y);creat(y,x);}scanf("%d%d",&s1,&e1);scanf("%d%d",&s2,&e2);memset(pre,0,sizeof(pre));bfs(s1,e1);hs[e1] = true;for(int i = pre[e1];i;i = pre[i])<span style="font-family: Arial, Helvetica, sans-serif;">//搜索完第一次，回溯访问每个经过的节点</span>hs[i] = true;//把节点用哈希表存储起来memset(pre,0,sizeof(pre));bfs(s2,e2);for(int i = pre[e2];i;i = pre[i]){if(hs[i])//如果和第一条路有冲突sum++;}if(hs[e2])//别忘了终点需要特判，因为bfs在找到最后一个节点就跳出了sum++;if(sum)printf("%d\n",sum);elseprintf("success\n");}return 0;
}
这篇关于SDUTOJ 3058 路线冲突问题 ——bfs记录路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
