路线冲突问题
题目描述
给出一张地图,地图上有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 算法分析:两次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;
}