poj_3256_Cow Picnic
2024-08-24 07:22:00
The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).
The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.
Input
Line 1: Three space-separated integers, respectively: K, N, and M
Lines 2..
K+1: Line
i+1 contains a single integer (1..
N) which is the number of the pasture in which cow
i is grazing.
Lines
K+2..
M+
K+1: Each line contains two space-separated integers, respectively
A and
B (both 1..
N and
A !=
B), representing a one-way path from pasture
A to pasture
B.
Lines 2..
K+1: Line
i+1 contains a single integer (1..
N) which is the number of the pasture in which cow
i is grazing.
Lines
K+2..
M+
K+1: Each line contains two space-separated integers, respectively
A and
B (both 1..
N and
A !=
B), representing a one-way path from pasture
A to pasture
B.
Output
Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.
Sample Input
2 4 4
2
3
1 2
1 4
2 3
3 4
Sample Output
2
Hint
The cows can meet in pastures 3 or 4.
dfs题,搜索每只牛能到达的位置。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000005
int prime[N];
int pn=0;
int vis[10005];
int st[10005];
int val[10005];
int a[10005];
int b[10005];
int h[10005];
int k,n,m;
void dfs(int x)
{
val[x]=1;vis[x]++;
for(int i=h[x];i;i=a[i])
{
if(!val[b[i]])
dfs(b[i]); }
}
int main()
{
//int k,n,m;
cin>>k>>n>>m;
int num=0;
for(int i=1;i<=k;i++)
{
cin>>st[i];
//vis[st[i]]++;
}
int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
a[i]=h[x];
b[i]=y;
h[x]=i; }
for(int i=1;i<=k;i++)
{
memset(val,0,sizeof(val));
dfs(st[i]);
}
for(int i=1;i<=n;i++)
{
if(vis[i]==k)
num++;
}
cout<<num<<endl;
}
最新文章
- LeetCode-3LongestSubstringWithoutRepeatingCharacters(C#)
- spring MVC @Resource不支持Lazy加载
- IIS 解决问题:HTTP 错误 401.1 - 未授权:登录失败
- Symantec System Recovery
- 【Spark学习】Apache Spark作业调度机制
- 欢迎来到Googny的博客
- Jmeter Constant Throughput Timer 使用
- (转) Spring读书笔记-----Spring的Bean之配置依赖
- pyqt中使用matplotlib绘制动态曲线 – pythonic
- Sql Server中如何快速修正SQL 语句错误
- [每日一题] OCP1z0-047 :2013-07-16 主键与唯一索引
- 算法模板——AC自动机
- 每天一个JS 小demo之个人信息添加。主要知识点:DOM操作中的表格操作,节点操作
- JavaScript匿名自执行函数~function(){}
- MongoDB系列:五、MongoDB Driver使用正确的姿势连接复制集
- HAAR与DLib的实时人脸检测之实现与对比
- portscaner 多线程、多协程并发端口扫描
- C/C++ 中嵌入 arm 汇编
- docker构建自定义镜像
- Mybatis学习总结(四)——输入映射和输出映射