社区讨论
求调(
P3916图的遍历参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhjrez0t
- 此快照首次捕获于
- 2025/11/04 07:16 4 个月前
- 此快照最后确认于
- 2025/11/04 07:16 4 个月前
记忆化40pts
不记忆化90pts(#8TLE)
CPP#include <bits/stdc++.h>
using namespace std;
const int max_=1e5+5;
struct node{
vector<int>v;
}a[max_];
int n,m,f[max_];
bool vis[max_];
int dfs(int x){
vis[x]=1;
if(f[x]){
return f[x];
}
int ans=x;
for(auto i:a[x].v){
if(!vis[i]){
ans=max(ans,dfs(i));
}
}
f[x]=ans;
return ans;
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].v.push_back(y);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
cout<<dfs(i)<<' ';
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...