请问为什么正向dfs 会tle?为什么一定要反向?
查看原帖
请问为什么正向dfs 会tle?为什么一定要反向?
443293
CHENchen13楼主2021/3/29 15:45

# include  <cstdio>
# include <vector>
# include <queue>
# include <cstring> 
using namespace std;
vector <int> a[100005];
bool vis[100005];

int dfs(int i,int maxx){
	vis[i]=1;
	if(a[i].empty())
		return maxx;
 	else for(int j=0;j<a[i].size();j++){
 		int p=a[i][j];         
 		maxx=max(maxx,p);
 		if(!vis[p])
 			maxx=dfs(p,maxx);
	 }	
	return maxx;
}



int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-')    f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
	
}

int n,m;
int main(){
	n=read();
	m=read();
	int x,y,maxx=0;
	for(int i=1;i<=m;i++){
		x=read();
		y=read();
		a[x].push_back(y);   
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis)); 
		if(a[i].empty())
			printf("%d ",i);
		else
	   		printf("%d ",dfs(i,i));
	}
	return 0;
} 
2021/3/29 15:45
加载中...