我一开始写了个这样的代码:
#include<cstdio>
#include<vector>
using namespace std;
const int MAXK=105,MAXN=1005;
int a[MAXK],ans[MAXN];
vector<int>edge[MAXN];
void dfs(int now) {
ans[now]++;
int len=edge[now].size();
for(int i=0;i<len;i++)
dfs(edge[now][i]);
}
int main() {
int k,n,m,x,y;
scanf("%d %d %d",&k,&n,&m);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++) {
scanf("%d %d",&x,&y);
edge[x].push_back(y);
}
for(int i=1;i<=k;i++)
dfs(a[i]);
int cnt=0;
for(int i=1;i<=n;i++) {
if(ans[i]==k)
cnt++;
}
printf("%d",cnt);
return 0;
}
https://www.luogu.com.cn/record/131704446
后来看第一篇题解和我差不多,于是我学习了一下:
#include<cstdio>
#include<vector>
using namespace std;
const int MAXK=105,MAXN=1005;
int a[MAXK],ans[MAXN];
bool vis[MAXN];
vector<int>edge[MAXN];
void dfs(int now) {
ans[now]++;
vis[now]=true;
int len=edge[now].size();
for(int i=0;i<len;i++) {
if(!vis[edge[now][i]])
dfs(edge[now][i]);
}
}
int main() {
int k,n,m,x,y;
scanf("%d %d %d",&k,&n,&m);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++) {
scanf("%d %d",&x,&y);
edge[x].push_back(y);
}
for(int i=1;i<=k;i++) {
for(int j=1;j<=n;j++)
vis[j]=false;
dfs(a[i]);
}
int cnt=0;
for(int i=1;i<=n;i++) {
if(ans[i]==k)
cnt++;
}
printf("%d",cnt);
return 0;
}
https://www.luogu.com.cn/record/131707793
令我不解的是,多开了一个vis数组空间会比原来大,为什么MLE->AC了呢?(悬关)