简单DFS)"/>
Milk Factory(简单DFS)
一简单DFS题
- 牛奶生意正红红火火!Farmer
John的牛奶加工厂内有N个加工站,编号为1…N(1≤N≤100),以及N−1条通道,每条连接某两个加工站。(通道建设很昂贵,所以FarmerJohn选择使用了最小数量的通道,使得从每个加工站出发都可以到达所有其他加工站)。 - 为了创新和提升效率,FarmerJohn在每条通道上安装了传送带。不幸的是,当他意识到传送带是单向的已经太晚了,现在每条通道只能沿着一个方向通行了!所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
- 然而,Farmer John认为事情可能还不算完全失败,只要至少还存在一个加工站i 满足从其他每个加工站出发都可以到达加工站i。注意从其他任意一个加工站j前往加工站i可能会经过i和j之间的一些中间站点。请帮助FarmerJohn求出是否存在这样的加工站i
输入格式
输入的第一行包含一个整数N,为加工站的数量。以下N−1行每行包含两个空格分隔的整数ai和bi,满足1≤ai,bi≤N以及ai≠bi。这表示有一条从加工站ai向加工站bi移动的传送带,仅允许沿从ai到bi的方向移动。
输出格式
如果存在加工站i
满足可以从任意其他加工站出发都可以到达加工站i,输出最小的满足条件的i。否则,输出−1
输出样例:
3
1 2
3 2
输出样例:
2
题目大意:n-1个单向路线,判读是否存在一个点能从其他任意点到达(中间可跨越);
分析:原来是想着用并查集做的,但是会导致某个点与其他点错误连接(合并的时候);可以用深搜解决;
思路:循环遍历每一个点是否符合,寻找该点的出发地,接着以该出发地为目的地寻找出发地。。。记录出发地的个数;
代码:
#include<iostream>
using namespace std;
int n,a[101],b[101],cnt;//a为出发地,b为目的地;
void dfs(int x)
{for(int i=1;i<n;i++){if(b[i]==x) //目的地为当前值; {cnt++;dfs(a[i]);}}
}
int main(){cin>>n;for(int i=1;i<n;i++) cin>>a[i]>>b[i];for(int i=1;i<=n;i++){cnt=0;dfs(i);if(cnt==n-1) //其他点都可到达; {cout<<i;return 0;}}cout<<-1;return 0;
}
很菜,导致这个入门的DFS都没想到,DFS的题处理的不够,得加强专题训练!
更多推荐
Milk Factory(简单DFS)
发布评论