社区讨论

求助,搞不定了

P3916图的遍历参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1unvgz
此快照首次捕获于
2023/10/23 03:16
2 年前
此快照最后确认于
2023/11/03 03:47
2 年前
查看原帖
u->v时,我的想法是利用dfs的回溯返回v可以到达的最大值,再将其与u可以到达的最大值比较更新maxTo[u]。 WA了很多发。不知为啥。
当测试数据为环,或者一个起点或者一个树的时候感觉都没有试出来错误。
下载了第一个测试点,有37个点,实在没法找错。
求助大佬!!!
CPP
#include <iostream>
using namespace std;

//链式前向星存图
const int MAXV=100010;
const int MAXE=100010;

struct Edge{
    int ne;
    int v;
    int w;
}e[MAXE];

int head[MAXV];
int MAXTO[MAXV];
bool Graph_vis[MAXV];
int Graph_cnt=1;
int MAXVGo(int u){
    if(Graph_vis[u]) return MAXTO[u];
    Graph_vis[u]=1;
    int max_get=u;
    MAXTO[u]=max({max_get,MAXTO[u]});
    for (int i=head[u]; ~i; i=e[i].ne) {
        MAXTO[u]=max({max_get,MAXVGo(e[i].v),MAXTO[u]});
    }
    return MAXTO[u];
}
void init(){
    for(int i=0;i<MAXV;i++) head[i]=-1;
    return;
}

void add(int u,int v,int w){
    e[Graph_cnt].w=w;
    e[Graph_cnt].v=v;
    e[Graph_cnt].ne=head[u];
    head[u]=Graph_cnt++;
    return;
}

void solve();

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; //cin>>T;
    T=1;
    while (T--) solve();
    return 0;
}
 
void solve(){
    int n,m;
    cin>>n>>m;
    init();
    
    for (int i=1; i<=m; i++) {
        int a,b;
        cin>>a>>b;
        add(a,b,0);
    }
    
    for (int i=1; i<=n; i++) {
        if(!Graph_vis[i]){
            MAXVGo(i);
        }
    }
    for (int i=1; i<=n; i++) {
        cout<<MAXTO[i]<<" ";
    }
    cout<<endl;
    
    return;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...