为什么在进入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;
}