P7771 【模板】欧拉路径 求助
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/12 16:50
  • 上次更新2023/10/28 06:45:48
查看原帖
P7771 【模板】欧拉路径 求助
439327
南瓜桐楼主2022/3/12 16:50
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
namespace wzl{
const int maxm = 2e5 + 1;
const int maxn = 1e5 + 1;
vector <int>e[maxm];
vector <bool>vst[maxm];
int ans[maxn]={},top=0;
int cd[maxn]={},rd[maxn]={};
int m,n;
int s;
bool f = true;
void dfs(int x){
	for(int i = 0; i < e[x].size(); ++i){
		int y = e[x][i];
		if(vst[x][i] == false){
			vst[x][i] = true;
			dfs(y);
//			vst[x][i] = false;
		}
		ans[++top] = x;
	}
	
	
//	cout<<x<<endl;
}
int start(){
	for(int i = 1;i <= n; ++i){
		int x = i;
		for(int j = 0; j < e[i].size(); ++j){
			int y = e[i][j];
			++cd[x];
			++rd[y];
		}
	}
	int nst = 0,ned = 0,st,ed;
	for(int i = 1; i <= n; ++i){
		if(rd[i] - cd[i] == 1){
			++ned;
			ed = i;
		}
		if(cd[i] - rd[i] == 1){
			++nst;
			st = i;
		}
		
	}
	if( !(ned == 1 && nst == 1) ){
		f = false;
	}
	return st;
}
void add(int u,int v){
	e[u].push_back(v);
	vst[u].push_back(false);
	return;
}
void main(){
	cin>>n>>m;
	for(int i = 1; i <= m; ++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i = 1; i <= n; ++i){
		sort(e[i].begin(),e[i].end());
	}
//	for(int i = 1; i <= n; ++i){
//		cout<<i<<": ";
//		for(int j = 0;j < e[i].size(); ++j){
//			cout<<e[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	s = start();
	if (f == false){
		cout<<"No"<<endl;
		return;
	}else{
		dfs(s);
	}
	for(int i = n; i >= 1; --i){
		cout<<ans[i]<<' ';
	}
	return;
}
}



int main(){
	wzl::main();
	return 0;
}
2022/3/12 16:50
加载中...