C++(g++ 7.5.0) 解法, 执行用时: 58ms, 内存消耗: 856K, 提交时间: 2022-08-21 20:05:51

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define coff ios::sync_with_stdio(0)
const int inf=0x3f3f3f3f;
const int inn=-(1<<30);
using namespace std;
const int N=50;
const int M=2005;
int g[N][M];
int mark[M];
int d[N];
int n,m;
int ans[M],cnt;
int st;
void init()
{
    n=m=0;
    memset(g,0,sizeof g);
    memset(d,0,sizeof d);
}
bool input()
{
    init();
    int a,b,c;
    cin>>a>>b;
    if(!a&&!b) return 0;
    cin>>c;
    n=max(n,max(a,b));
    st=min(a,b);
    g[a][c]=b;
    g[b][c]=a;
    d[a]++;
    d[b]++;
    m++;
    while(cin>>a>>b)
    {
        if(!a&&!b) break;
        cin>>c;
        n=max(n,max(a,b));
        g[a][c]=b;
        g[b][c]=a;
        d[a]++;
        d[b]++;
        m++;
    }
    return 1;
}
void dfs(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(g[x][i]&&!mark[i])
        {
            mark[i]=1;
            dfs(g[x][i]);
            ans[++cnt]=i;
        }
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(d[i]%2)
        {
            puts("Round trip does not exist.");
            return;
        }
    }
    memset(mark,0,sizeof mark);
    cnt=0;
    dfs(st);
    for(int i=m;i>=1;i--)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}
int main()
{
    while(input())
    {
        solve();
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 888K, 提交时间: 2019-09-11 23:12:03

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M=45;
const int N=1995;
int gra[M][N]; //gra[i][j]=k表示点x经过边j到达点k
int ind[M]; //每个节点的度
int ans[N],cnt; //最佳方案
bool vis[N]; //标记每条街道是否被访问
int maxn; //纪录最大的街道编号
void dfs(int s)
{
    for(int i=1;i<=maxn;i++)
      if(gra[s][i]&&!vis[i])
      {
          vis[i]=true;
          dfs(gra[s][i]);
          ans[cnt++]=i;
      }
}
int main()
{
    int start;
    int u,v,w;
    while(scanf("%d%d",&u,&v))
    {
        if(u==0&&v==0) break;
        start=min(u,v);
        maxn=0;
        cnt=0;
        memset(gra,0,sizeof(gra));
        memset(ind,0,sizeof(ind));
        memset(vis,false,sizeof(vis));
        while(u!=0&&v!=0)
        {
            scanf("%d",&w);
            gra[u][w]=v;
            gra[v][w]=u;
            ind[u]=!ind[u]; //我们只需要纪录度数的奇偶性即可
            ind[v]=!ind[v];
            maxn=max(maxn,w);
            scanf("%d%d",&u,&v);
        }
        int k=1;
        for(;k<M;k++) //查找节点度数为偶数的点
          if(ind[k]) break;
        if(k<M)
        {
            puts("Round trip does not exist.");
            continue;
        }
        dfs(start);
        for(int i=cnt-1;i>=0;i--)
          printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 20ms, 内存消耗: 888K, 提交时间: 2019-12-11 15:53:26

#include<bits/stdc++.h>
using namespace std;
int Start,t,t1,t2,Top,Num[45],Step[1995],Map[45][1995],Edge[45][1995];
bool Mark[1995];
void DFS(int t) {
	for (int a=1; a<=Num[t]; a++) {
		int S=Edge[t][a];
		if (!Mark[S]) {
			int T=Map[t][S];
			Mark[S]=true;
			DFS(T);
			Step[++Top]=S;
		}
	}
}
int main() {
	while (scanf("%d%d",&t1,&t2)!=EOF) {
		if (!t1&&!t2)
			break;
		memset(Num,0,sizeof(Num));
		scanf("%d",&t);
		Start=min(t1,t2);
		Edge[t1][++Num[t1]]=t;
		Edge[t2][++Num[t2]]=t;
		Map[t1][t]=t2;
		Map[t2][t]=t1;
		while (scanf("%d%d",&t1,&t2)!=EOF) {
			if (!t1&&!t2)
				break;
			scanf("%d",&t);
			Edge[t1][++Num[t1]]=t;
			Edge[t2][++Num[t2]]=t;
			Map[t1][t]=t2;
			Map[t2][t]=t1;
		}
		int T;
		for (T=1;; T++)
			if (!Num[T]||Num[T]&1)
				break;
		if (Num[T]) {
			puts("Round trip does not exist.");
			continue;
		}
		int Max=T-1;
		for (T=1; T<=Max; T++)
			sort(Edge[T]+1,Edge[T]+Num[T]+1);
		memset(Mark,0,sizeof(Mark));
		Top=0;
		DFS(Start);
		for (T=Top; T>1; T--)
			printf("%d ",Step[T]);
		printf("%d\n",Step[T]);
	}
	return 0;
}