当前位置: 代码迷 >> 综合 >> POJ 3256 Cow Picnic  DFS图的遍历
  详细解决方案

POJ 3256 Cow Picnic  DFS图的遍历

热度:67   发布时间:2024-01-15 08:01:05.0

Cow Picnic

Time Limit: 2000MS

 

Memory Limit: 65536K

Total Submissions: 5933

 

Accepted: 2445

Description

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: KN, 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.

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.

Source

USACO 2006 December Silver

算法分析:

题意:

给你个有向图,k个起点,遍历全图,问从k个起点出发都能遍历到节点的个数。

分析:

K遍dfs遍历全图,记录每个节点被访问的次数,如果cnt【i】==k则表明都能访问到。

代码实现:

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INT_INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN = 1e5 + 10;  
const int MAXT = 10000 + 10;  
const int M=10010;
int vis[M],cnt[M];
vector<int>v[M];
void dfs(int n)
{cnt[n]++;        //统计到达该点个数vis[n]=1;for(int i=0;i<v[n].size();i++){if(!vis[v[n][i]])dfs(v[n][i]);}
}int main()
{int k,m,n;while(scanf("%d%d%d",&k,&n,&m)!=EOF){int a[M];for(int i=1;i<=m;i++){v[i].clear();} for(int i=1;i<=k;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);v[x].push_back(y);}memset(cnt,0,sizeof(cnt));for(int i=1;i<=k;i++){memset(vis,0,sizeof(vis));dfs(a[i]);}int ans=0;for(int i=1;i<=n;i++){if(cnt[i]==k) ans++;}printf("%d\n",ans);}return 0;
}