求解释(问题在代码里)
查看原帖
求解释(问题在代码里)
688956
daitangchen2008楼主2024/7/20 02:54
#include<bits/stdc++.h>
using namespace std;
int din[1000005],dout[1000005];
int del[1000005];
stack <int> sta;
vector<int>edge[500005];
int n,m;
void dfs(int x)
{
	for(int i=del[x];i<edge[x].size();i=del[x])
	{
		del[x]=i+1;
		dfs(edge[x][i]);
	}
  /*
  为什么这段dfs改写为
  for(int i=del[x];i<edge[x].size();i++)//改成i++
  {
  		del[x]=i+1;
       dfs(edge[x][i]);
   }会挂*/
	sta.push(x);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		din[x]++;
		dout[y]++;
	}
	int st=1,en=n;
	for(int i=1;i<=n;i++)
	{
		if(din[i]-dout[i]==1)
		{
			if(st==1)
				st=i;
			else
				{
					cout<<-1<<endl;
					return 0;
				}
		}
		if(din[i]-dout[i]==-1)
		{
			if(en==n)
				en=i;
			else
			{
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	sort(edge[i].begin(),edge[i].end());
	dfs(st);
	while(!sta.empty())
	{
		cout<<sta.top()<<' ';
		sta.pop();
	}
	return 0;
} 
2024/7/20 02:54
加载中...