关于当前弧优化有个问题请教
查看原帖
关于当前弧优化有个问题请教
1122530
elpsconr楼主2024/8/6 19:59

为什么i=e[i].ne会tle,而i=h[x]就不会?不是已经把e[i].ne赋值给h[x]了嘛,那我i=e[i].ne和i=h[x]应该没有区别啊,但是结果告诉我有很大区别,求解为什么两者不一样

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define cy cout<<"YES"<<endl
#define cn cout<<"No"<<endl
#define l(rt) rt<<1
#define r(rt) rt<<1|1
const int N=3e5+6,yyx=4e9+7;
int n,m,h[N],d[N][2],idx,vis[N];
struct node{
    int to,ne;
    bool operator< (const node& w)const{
        if(to==w.to) return ne>w.ne;
        return to<w.to;
    }
}e[N<<1],a[N<<1];
void add(int u,int v){
   e[idx].to=v;e[idx].ne=h[u];h[u]=idx++;
}
stack<int> st;
void dfs(int x){
    for(int i=h[x];~i;i=h[x]){//不会tle
        h[x]=e[i].ne;
        dfs(e[i].to);
    }
    // for(int i=h[x];~i;i=e[i].ne){//会tle
    //     h[x]=e[i].ne;
    //     dfs(e[i].to);
    // }
    st.push(x);
}
inline void solve(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;++i){
       cin>>a[i].to>>a[i].ne;d[a[i].to][0]++,d[a[i].ne][1]++;
    }
    int k=0,j=0,s=1;
    for(int i=1;i<=n;++i){
        if(abs(d[i][0]-d[i][1])>1){
            cn;return;
        }
        if(d[i][0]-d[i][1]==1) ++k,s=i;
        else if(d[i][1]-d[i][0]) ++j;
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m;++i){
        add(a[i].to,a[i].ne);
    }
    if(!(j^k)){
        dfs(s);
        while(st.size()) cout<<st.top()<<" ",st.pop();
    }
    else cn;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int _=1;
   //cin>>_;
    while(_--)
    solve();
    return 0;
}
2024/8/6 19:59
加载中...