求助欧拉路径!!
查看原帖
求助欧拉路径!!
143742
Nelson_Wang楼主2021/10/11 14:39
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct EDGE{
	int to, f;
	bool operator<(const EDGE &Y)const{
		return to < Y.to;
	}
};

int n, m, in[N], out[N], S, T, nex[N];
vector<int> ans;
vector<EDGE> e[N];

void dfs(int x){
	for(int i=nex[x]; i<e[x].size(); ++i){
		e[x][i].f = 1;
		nex[x] = i+1;
		dfs(e[x][i].to);
	}
	ans.push_back(x);
}
int main(){
	// freopen("input.txt", "r", stdin);
	scanf("%d%d", &n, &m);
	while(m--){
		int a, b; scanf("%d%d", &a, &b);
		e[a].push_back((EDGE){b, 0});
		in[b]++, out[a]++;
	}
	for(int i=1; i<=n; ++i){
		if(in[i]+1==out[i]){
			if(S)
				return puts("No"), 0;
			S = i;
		}
		else if(in[i]-1==out[i]){
			if(T)
				return puts("No"), 0;
			T = i;
		}
		else if(in[i]!=out[i])
			return puts("No"), 0;
	}
	for(int i=1; i<=n; ++i)
		sort(e[i].begin(), e[i].end());
	dfs(S);
	for(int i=ans.size()-1; ~i; --i)
		printf("%d ", ans[i]);
	return 0;
}
2021/10/11 14:39
加载中...