NC25098. [USACO 2006 Dec S]Cow Picnic
描述
输入描述
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.
输出描述
Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.
示例1
输入:
2 4 4 2 3 1 2 1 4 2 3 3 4
输出:
2
说明:
4<--3C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 492K, 提交时间: 2019-06-25 15:23:27
#include <bits/stdc++.h>
using namespace std;
vector<int>G[1005];
bool vis[1005];
int k,n,m;
int pos[105];
int cnt[1005];
void dfs(int x){
cnt[x]++;
for(int i=0;i<G[x].size();++i){
int v = G[x][i];
if(!vis[v]){
vis[v] = 1;
dfs(v);
}
}
}
int main(){
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=k;++i) scanf("%d",&pos[i]);
int x,y;
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
for(int i=1;i<=k;++i){
memset(vis,0,sizeof(vis));
vis[pos[i]] = 1;
dfs(pos[i]);
}
int ans = 0;
for(int i=1;i<=n;++i){
if(cnt[i]>=k) ans++;
}
printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 115ms, 内存消耗: 1628K, 提交时间: 2019-07-03 20:30:40
#include<bits/stdc++.h>
using namespace std;
bool f[1010][1010],dp[110][1010],dp2[1010];
int n,m,k,a[110];
void dfs(int i,int x){
dp[i][x]=true;
for(int j=1;j<=n;j++)
if(f[x][j]&&!dp[i][j])dfs(i,j);
}
int main(){
cin>>k>>n>>m;
for(int i=1;i<=k;i++)
cin>>a[i];
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
f[a][b]=true;
}
for(int i=1;i<=k;i++)
dfs(i,a[i]);
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
if(!dp[i][j])dp2[j]=true;
int ans=0;
for(int i=1;i<=n;i++)
if(!dp2[i])ans++;
cout<<ans<<"\n";
return 0;
}