悬赏关注!!!记忆化搜索写wa了
  • 板块P3916 图的遍历
  • 楼主RanHT
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/7/7 21:07
  • 上次更新2023/11/3 11:08:00
查看原帖
悬赏关注!!!记忆化搜索写wa了
881471
RanHT楼主2023/7/7 21:07
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[8]={-1,0,1,0};
int dy[8]={0,1,0,-1};
const int N=2e5+10,mod=80112002;
string s;
char z1,z2;
int  len,m,a,b,c,d,k,x,y,rd[N],cd[N],n,dp[N],f[N],bj[N],h[N],ne[N],e[N];
ll idx;
int res=-1e9,ans=0x3f3f3f3f;
vector<int>v1,v2;
//typedef pair<int,int> pp;
queue<int>q;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
int dfs(int x)
{
	if(dp[x]){
		return dp[x];
	}
	int num=x;
	for(int i=h[x];i!=-1;i=ne[i]){
		int j=e[i];
		if(!bj[j]){
			bj[j]=1;
			num=max(num,j);
			num=max(num,dfs(j));
			bj[j]=0;
		}
	}
	return dp[x]=num;
}
int main()
{
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		h[i]=-1;
	}
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
		dfs(i);
	}
	for(int i=1;i<=n;i++){
		cout<<dp[i]<<' ';
	}
	return 0;	
}
2023/7/7 21:07
加载中...