一个关于dfs输出方式的问题
查看原帖
一个关于dfs输出方式的问题
1409299
caisien楼主2025/8/29 14:06

为什么在进入dfs时输出当时节点只有20分

#include <bits/stdc++.h>

using namespace std;

int n,m,in[100005],out[100005],sta,cnt,nw[100005];
vector<int>v[100005];

void dfs(int s){
    cout << s << " ";//直接输出
    for(int i = nw[s];i < v[s].size();i = nw[s]){
        nw[s]++;
        int son = v[s][i];
        dfs(son);
    }
}

signed main() {
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        out[a]++;
        in[b]++;
    }
    for(int i = n;i >= 1;i--){
        sort(v[i].begin(),v[i].end());
        if(out[i] - in[i] == 1){
            sta = i,cnt++;
        }else if(in[i] - out[i] == 1){
            cnt++;
        }else if(in[i] == out[i]){
            continue;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    if(cnt > 2){
        cout << "No" << endl;
        return 0;
    }
    dfs(sta);
    return 0;
}

而在最后存储到stack,从dfs出来后输出才对

#include <bits/stdc++.h>

using namespace std;

stack<int>ans;
int n,m,in[100005],out[100005],sta = 1,cnt,nw[100005];
vector<int>v[100005];

void dfs(int s){
    for(int i = nw[s];i < v[s].size();i = nw[s]){
        nw[s]++;
        int son = v[s][i];
        dfs(son);
    }
    ans.push(s);//最后存储
}

signed main() {
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        out[a]++;
        in[b]++;
    }
    for(int i = 1;i <= n;i++){
        sort(v[i].begin(),v[i].end());
        if(out[i] - in[i] == 1){
            sta = i,cnt++;
        }else if(in[i] - out[i] == 1){
            cnt++;
        }else if(in[i] == out[i]){
            continue;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    if(cnt > 2){
        cout << "No" << endl;
        return 0;
    }
    dfs(sta);
    while(!ans.empty()){//stack输出
        cout << ans.top() << " ";
        ans.pop();
    }
    return 0;
}
2025/8/29 14:06
加载中...