社区讨论

求调(

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 条回复,欢迎继续交流。

正在加载回复...