AC后的疑问
查看原帖
AC后的疑问
1008513
xiaoshumiao楼主2023/10/27 15:23

我一开始写了个这样的代码:

#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了呢?(悬关)

2023/10/27 15:23
加载中...