对代码的疑惑
查看原帖
对代码的疑惑
1145602
dongzhenmao楼主2024/8/1 16:48

如果使用数组记录每个节点的大小,只有 30pts30 pts

#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define lnt long long
#define inf 0x3f3f3f3f
using namespace std;
int xx;char ff,chh;inline int read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=1e3;
int win[N],lose[N],n,m,ans;
vector<int> G[N],F[N];
bool vis1[N],vis2[N],vis[N];
void dfs1(int);void dfs2(int);
int main(){
	n=read();m=read();
	for(int i=0;i<m;++i){
        int x=read(),y=read();
        G[x].push_back(y);
        F[y].push_back(x);
    }
    for(int i=1;i<=n;++i){win[i]=lose[i]=1;}
    for(int i=1;i<=n;++i){
		if(G[i].size()==0){
			dfs2(i);
		}
		if(F[i].size()==0){
			dfs1(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(win[i]+lose[i]==n+1){
			ans++;
		}
	}
   	printf("%d",ans);
    return 0;
}
void dfs1(int x){
	if(vis1[x]){return;}
	for(auto to: G[x]){
		if(!vis1[to]){dfs1(to);}
		if(!vis1[to]){win[x]+=win[to];vis1[to]=1;}
	}
}
void dfs2(int x){
	if(vis2[x]){return;}
	for(auto to: F[x]){
		if(!vis2[to]){dfs2(to);}
		if(!vis2[to]){lose[x]+=lose[to];vis2[to]=1;}
	}
}

但是改用不优化的版本,却满了:

#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define lnt long long
#define inf 0x3f3f3f3f
using namespace std;
int xx;char ff,chh;inline int read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=1e3;
int win[N],lose[N],n,m,ans,s1,s2;
vector<int> G[N],F[N];
bool vis1[N],vis2[N],vis[N];
void dfs1(int);
void dfs2(int);
int main(){
	n=read();m=read();
	for(int i=0;i<m;++i){
        int x=read(),y=read();
        G[x].push_back(y);
        F[y].push_back(x);
    }
    for(int i=1;i<=n;++i){win[i]=lose[i]=1;}
    for(int i=1;i<=n;++i){
    	s1=s2=0;
		dfs2(i);
		dfs1(i);
		memset(vis2,0,sizeof(vis1));
		memset(vis1,0,sizeof(vis1));
		if(s1+s2==n+1){ans++;}
	}
   	printf("%d",ans);
    return 0;
}
void dfs1(int x){
	if(vis1[x]){return;}
	vis1[x]=1;s1++;
	for(auto to: G[x]){
		dfs1(to);
	}
}
void dfs2(int x){
	if(vis2[x]){return;}
	vis2[x]=1;s2++;
	for(auto to: F[x]){
		dfs2(to);
	}
}

想知道为什么

2024/8/1 16:48
加载中...