救命,感觉跟题解差不多,但是就是有数据错误 ,
查看原帖
救命,感觉跟题解差不多,但是就是有数据错误 ,
629571
nicole_coco楼主2022/4/17 23:56
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<cstring> 
using namespace std;
const int maxn=1e5+5;
vector<vector<int> >data;
//用于存图 如果有1->2 1->3则data[1]中为2 3 ,分别为data[1][2] data[1][3] 
int now[maxn],degree[maxn],sx=1;
//now为当前下标,如果now[1]=0时(以上例),则指向点2
//degree为某个点出度和入度的相对大小,为出度的话减一,为入度的话加一 
stack<int>ans;
//ans栈用于存储答案 
void dfs(int num)
{
	int len=data[num].size();
	for(int i=now[num];i<len;i=now[num])
	{
		now[num]=i+1;//下标的值进行变动 
		dfs(data[num][i]);
	}
	ans.push(num);
}
int main()
{
	int n,m,u,v;
	scanf("%d%d",&n,&m);
	//n为点的个数,m为边的个数 
	data.resize(n+1);
	while(m--)
	{
		scanf("%d%d",&u,&v);//u->v 
		data[u].push_back(v);
		--degree[u];//这条边对u来说时出度,减一 
		++degree[v];//这条边对v来说时入度,加一 
	}
	int num1=0,num2=0;
	//分别时出度大于入度一的个数,入度大于出度的个数 
	for(int i=1;i<=n;i++)
	{
		if(degree[i]==-1)
      //出度大于入度,也就是起点 
		{
			++num1;sx=i;
		}
		else if(degree[i]==1)++num2;
     //入度大于出度 
		else if(degree[i]!=0) 
		{
			printf("No\n");
			return 0;
		}
	}
	if(!(num1==1&&num2==1))//不满足条件,直接No 
	{
		printf("No\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		sort(data[i].begin(),data[i].end());
     //进行排列,因为需要输出字典序最小的 
	}
	dfs(sx);
	while(!ans.empty())//输出答案 
	{
		printf("%d ",ans.top());
		ans.pop();
	}
}
2022/4/17 23:56
加载中...