rt,以下两个代码只有第10行i的更新不一样,为什么第一个AC而第二个只有十分?
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,in[maxn],out[maxn];
vector<int> e[maxn],vis[maxn];
int begin1[maxn];
stack<int> st;
void dfs(int now)
{
for(int i=begin1[now];i<e[now].size();i=begin1[now])
{
begin1[now]=i+1;
dfs(e[now][i]);
}
st.push(now);
}
int main()
{
ios::sync_with_stdio(false);
cin >>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin >>x>>y;
e[x].push_back(y);
vis[x].push_back(0);
out[x]++,in[y]++;
}
bool f1=false,f2=false,f=false;
int s=0;
for(int i=1;i<=n;i++)
{
if(in[i]==out[i])
continue;
if(in[i]==out[i]+1)
{
if(f2)
f=1;
else
f2=1;
}
else if(in[i]+1==out[i])
{
if(f1)
f=1;
else
f1=1,s=i;
}
else
f=1;
}
if(f)
{
cout <<"No"<<endl;
return 0;
}
for(int i=1;i<=n;i++)
sort(e[i].begin(),e[i].end());
if(!f1)
s=1;
dfs(s);
while(!st.empty())
{
cout <<st.top()<<" ";
st.pop();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,in[maxn],out[maxn];
vector<int> e[maxn],vis[maxn];
int begin1[maxn];
stack<int> st;
void dfs(int now)
{
for(int i=begin1[now];i<e[now].size();i++)
{
begin1[now]=i+1;
dfs(e[now][i]);
}
st.push(now);
}
int main()
{
ios::sync_with_stdio(false);
cin >>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin >>x>>y;
e[x].push_back(y);
vis[x].push_back(0);
out[x]++,in[y]++;
}
bool f1=false,f2=false,f=false;
int s=0;
for(int i=1;i<=n;i++)
{
if(in[i]==out[i])
continue;
if(in[i]==out[i]+1)
{
if(f2)
f=1;
else
f2=1;
}
else if(in[i]+1==out[i])
{
if(f1)
f=1;
else
f1=1,s=i;
}
else
f=1;
}
if(f)
{
cout <<"No"<<endl;
return 0;
}
for(int i=1;i<=n;i++)
sort(e[i].begin(),e[i].end());
if(!f1)
s=1;
dfs(s);
while(!st.empty())
{
cout <<st.top()<<" ";
st.pop();
}
return 0;
}