记忆化搜索(TLE)为啥会和 反向建图+dfs 差这么多呢?
查看原帖
记忆化搜索(TLE)为啥会和 反向建图+dfs 差这么多呢?
881751
nforget楼主2023/7/31 23:41
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int f[N];
vector<int> G[N];
int res=0;
int dfs(int u)
{
	if(f[u]) return f[u];
	int ans=u;
	for(auto x:G[u]){
		ans=max(ans,dfs(x));
	}
	return f[u]=ans;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int v,u;
		scanf("%d%d",&v,&u);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		printf("%d ",dfs(i));
	puts("");
	
	return 0;
}
2023/7/31 23:41
加载中...