60pts求条
查看原帖
60pts求条
752094
MornHus楼主2023/10/11 21:41
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,m;
int goes[maxn];
int ind[maxn];
int outd[maxn];
vector<int>g[maxn];
//先判定是否存在 
int s,t;
bool judge(){
	int a=0,b=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(ind[i]==outd[i]){
			cnt++;
		}
		else if(ind[i]-1==outd[i]){
			b++;
			t=i;
		}
		else if(outd[i]-1==ind[i]){
			a++;
			s=i;
		}
		else{
			return 0;
		}
	}
	if((cnt==n-2&&a==1&&b==1)||(cnt==n))return 1;
	return 0;
}
stack<int>ans;
void dfs(int now){
	for(int i=goes[now];i<g[now].size();i=goes[now]){
		goes[now]=i+1;
		dfs(g[now][i]);
	}
	ans.push(now);
}
int main(){
	n=read();
	m=read();
	for(int i=1,u,v;i<=m;i++){
		u=read();
		v=read();
		ind[v]++;
		outd[u]++;
		g[u].push_back(v);
	} 
	for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
	if(!judge()){
		cout<<"No";
		return 0;
	}
	dfs(s);
	while(!ans.empty()){
		cout<<ans.top()<<' ';
		ans.pop();
	}
	return 0;
}
2023/10/11 21:41
加载中...