C++14(g++5.4) 解法, 执行用时: 83ms, 内存消耗: 15896K, 提交时间: 2020-08-07 20:26:15

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
struct edge {
	int to, next;
}e[M * 2];
int head[N], idx;
bool st[M * 2];
int din[N], dout[N], type, n, m;
vector<int> res;
int cnt;

void add(int u, int v) {
	e[idx] = {v, head[u]};
	head[u] = idx++;
}

bool check() {
	if(type == 1) {
		for(int i = 1; i <= n; i++) {
			if(din[i] + dout[i] & 1) return false;
		}
	}
	else {
		for(int i = 1; i <= n; i++) {
			if(din[i] != dout[i]) return false;
		}
	}
	return true;
}

void dfs(int u) {
	for(int &i = head[u]; ~i;) {
		if(st[i]) {
            i = e[i].next;
            continue;
        }
		st[i] = true;
		if(type == 1) st[i ^ 1] = true;
		int x;
		if(type == 1) {
			x  = i / 2 + 1;
			if(i & 1) x = -x;
		}
		else x = i + 1;
		int v = e[i].to;
        i = e[i].next;
        dfs(v);
		res.push_back(x);
	}
}

void solve() {
	memset(head, -1, sizeof head);
	scanf("%d", &type);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v);
		dout[u]++; din[v]++;
		if(type == 1) {
			add(v, u);
		}
	}
	if(!check()) {
		puts("NO");
		return;
	}
	for(int i = 1; i <= n; i++) {
		if(head[i] != -1) {
			dfs(i);
			break;
		}
	}
	if(res.size() != m) puts("NO");
	else {
		puts("YES");
		for(int i = res.size() - 1; i >= 0; i--) {
			printf("%d ", res[i]);
		}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	solve();
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 103ms, 内存消耗: 19784K, 提交时间: 2022-10-03 10:29:07

#include<bits/stdc++.h>

using namespace std;
const int N=100010,M=400010;

int n,m,type;
int h[N],e[M],ne[M],idx;
int din[N],dout[N];
bool used[M];
vector<int> res;

void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
	din[b]++,dout[a]++;
}

void dfs(int u){
	for(int &i=h[u];~i;){
		if(used[i]){
			i=ne[i];
			continue;
		}
		used[i]=true;
		if(type==1)used[i^1]=true;//删反边 
		int t;//边编号
		if(type==1){
			t=i/2+1;
			if(i&1)t=-t; 
		}
		else t=i+1;
		int j=e[i];
		i=ne[i];
		dfs(j);
		res.push_back(t);
	}
}

int main(){
	scanf("%d%d%d",&type,&n,&m);
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		if(type==1)add(b,a);
		din[b]++,dout[a]++;
	}
	if(type==1){
		for(int i=1;i<=n;i++){
			if((din[i]+dout[i])&1){
				puts("NO");
				return 0;
			}
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(din[i]!=dout[i]){
				puts("NO");
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(~h[i]){
			dfs(i);
			break;
		}
	}
	if(res.size()<m)puts("NO");
	else{
		puts("YES");
		for(int i=res.size()-1;i>=0;i--)printf("%d ",res[i]);
		printf("\n");
	}
	return 0;
}