P7771 【模板】欧拉路径

求有向图欧拉路径,且字典序最小。所以我们要用vector存图后排序

const int N=1e5+79;
int in[N],ot[N];
int n,m;
std::vector<int> ans;
int del[N];
std::vector<int> v[N];

inline void dfs(int x){
	for(int i=del[x];i<v[x].size();i=del[x]){
		del[x]=i+1;
		dfs(v[x][i]);
	}
	ans.push_back(x);
}

int main(){
	read(n);read(m);
	int x,y;
	rep(i,1,m){
		read(x);read(y);
		v[x].push_back(y);
		++in[y];++ot[x];
	}
	rep(i,1,n){
		std::sort(v[i].begin(),v[i].end());
	}
	int s(1);//不能为0,如果是欧拉回路,这个值就不会变 
	int sum1(0),sum2(0),sum3(0);
	bool flag(1);//判断是不是欧拉回路 
	rep(i,1,n){
		
		if(ot[i]-in[i]==1){
			++sum1;
		}else if(ot[i]-in[i]==-1){
			++sum2;
		}
		if(ot[i]==in[i]){
			++sum3;
		}else {
			flag=0;
		}
	}
	if((sum1!=1||sum2!=1||sum3!=n-2)&&!flag ){
		puts("No");
		return 0;
	}
	
	rep(i,1,n){
		if(ot[i]-in[i]==1){
			s=i;
			break;
		}
	}
	dfs(s);
	reverse(ans.begin(),ans.end());
	for(auto i:ans){
		cout<<i<<' ';
	}
	return 0;
}
上一篇:Python的从0到1(九)-Python的数字类型(1)


下一篇:Windows常用cmd命令