John's trip POJ - 1041(这题数据有点水)

时间:2022-11-25 12:22:10

题意:

  其实还是一个欧拉回路,但要按字典序走路;

解析:

  我真是蠢啊emm。。。

  map[i][j]表示由顶点i经街道j会到达的顶点编号

   然后枚举j就好了 用栈储存。。

虽然我不是这样写的

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define pd(a) printf("%d\n", a);
#define plld(a) printf("%lld\n", a);
#define pc(a) printf("%c\n", a);
#define ps(a) printf("%s\n", a);
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff; int deg[maxn], vis[maxn];
int way[][maxn];
set<int> G[maxn];
stack<int> ss; void dfs(int u)
{
for(set<int>::iterator it = G[u].begin(); it != G[u].end(); it++)
{
int id = *it;
int v = way[u][id];
if(!vis[id])
{
vis[id] = ;
dfs(v);
ss.push(id);
}
}
} void fleury(int u)
{
dfs(u);
} void print()
{
int sh = ;
while(!ss.empty())
{
if(sh++) cout << " ";
cout << ss.top();
ss.pop();
}
cout << endl;
} int main()
{
int u, v, id;
while(scanf("%d%d", &u, &v) && u + v)
{
mem(deg, );
mem(vis, );
for(int i = ; i < ; i++) G[i].clear();
mem(way, );
int s = INF;
cin >> id;
way[u][id] = v;
way[v][id] = u;
G[u].insert(id);
G[v].insert(id);
s = min(s, u);
s = min(s, v);
deg[u]++;
deg[v]++;
while(scanf("%d%d", &u, &v) && u + v)
{
cin >> id;
way[u][id] = v;
way[v][id] = u;
G[u].insert(id);
G[v].insert(id);
s = min(s, u);
s = min(s, v);
deg[u]++;
deg[v]++;
}
int ans = ;
for(int i = ; i <= ; i++)
if(deg[i] & ) ans++;
if(ans == )
{
fleury(s);
print();
}
else
cout << "Round trip does not exist." << endl;
} return ;
}