P7771 欧拉路径模板求助
  • 板块灌水区
  • 楼主南瓜桐
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/15 22:08
  • 上次更新2023/10/28 06:30:16
查看原帖
P7771 欧拉路径模板求助
439327
南瓜桐楼主2022/3/15 22:08
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
namespace wzl{
int n,m;
const int maxn = 1e5 + 1;
const int maxm = 2e5 + 1;
int ans[maxn]={},top=0;
vector <int> map[maxn];
vector <bool> vst[maxn];
int cd[maxn]={},rd[maxn]={};
int s;
void add(int u,int v){
	map[u].push_back(v);
	vst[u].push_back(false);
	++cd[u];
	++rd[v];
	return;
}
int start(){
	int st=0;
	int nst=0,ned=0; 
	for(int i = n; i >= 0; --i){
		if(cd[i] - rd[i] == 1){
			++nst;
			st = i;
		}
		if(rd[i] - cd[i] == 1){
			++ned;
		}

	}
	if( (ned == 1 && nst == 1) || (ned == 0 && nst == 0) ){
		return st;
	}else{
		return -1;
	}
}
void dfs(int x){
//	cout<<x<<endl;
	for(int i = 0; i < map[x].size(); ++i){
		int y = map[x][i];
		if(vst[x][i] == false){
			vst[x][i] = true;
			dfs(y);
		}
	}
//	cout<<x<<' ';
	ans[++top] = x;
	return;
}
void main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	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(map[i].begin(),map[i].end());
	}
//	for(int i = 1; i <= n; ++i){
//		cout<<i<<":";
//		for(int j = 0; j < map[i].size(); ++j){
//			cout<<map[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	
	int s = start();
	if(s == -1){
		cout<<"No";
		return;
	}else{
//		cout<<s<<endl;
		dfs(s); 
	}
	for(int i = top; i >=1; --i){
		cout<<ans[i]<<' ';
	}
	return;
}
}


int main(){
	wzl::main();
	return 0;
}

Orz

2022/3/15 22:08
加载中...