记忆化DFs 90 ,TLE#1
查看原帖
记忆化DFs 90 ,TLE#1
1101266
Fe_CuSO4__FeSO4_Cu楼主2024/10/3 14:15
#include <bits/stdc++.h>
using namespace std;
vector<int>a[110000];
bool v[110000];
int ans[110000];
int n,m;
void dfs(int beg,int end)
{
    if(ans[beg]==n||a[end].empty()) return;
	for(int i=0;i<a[end].size();i++)
	{
		if(!v[a[end][i]])
		{
		    ans[beg]=max(ans[beg],a[end][i]);
		    v[a[end][i]]=1;
			dfs(beg,a[end][i]);
		}
	}
}
int main()
{
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
	    ans[i]=i;
		v[i]=1;
		dfs(i,i);
		v[i]=0;
		cout<<ans[i]<<" ";
		memset(v,0,sizeof(v));
	}
	return 0;
}
2024/10/3 14:15
加载中...