如果使用数组记录每个节点的大小,只有 30pts
#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);
}
}
想知道为什么