洛谷P1341《无序字母对》

一月 21, 2019 3890

欧拉图板子题

题目描述

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入输出格式

输入格式

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

输入输出样例

输入样例

1
2
3
4
5
4
aZ
tZ
Xt
aX

输出样例

1
XaZtX

说明

【数据规模与约定】

不同的无序字母对个数有限，n的规模可以通过计算得到。

解题思路

我们考虑把每一对字母视为一条边
那么这个图就是无向的（因为字母对是无序的）

题目让你求一个串，使得这个串里出现了所有的字母对，实际上就是让你求一条路径，使得所有的边都出现过

那这不就是求欧拉路吗！

所以这道题就完美地被转换为了欧拉路板子题

没学过欧拉路的看这里

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 256 + 233;
    
    int n;
    int G[MAXN][MAXN], deg[MAXN];
    char __MIN_NODE = 127, __MAX_NODE = 0;
    
    std::stack<char> stk;
    
    inline void addEdge(char prev, char next, bool Undirected = true) {
        ++G[prev][next];
        if (Undirected) addEdge(next, prev, false);
    }
    
    inline void deleteEdge(char prev, char next, bool Undirected = true) {
        --G[prev][next];
        if (Undirected) deleteEdge(next, prev, false);
    }
    
    inline void Hierholzer(char s) {
        for (char i = __MIN_NODE; i <= __MAX_NODE; ++i) {
            if (G[s][i]) {
                deleteEdge(s, i);
                Hierholzer(i);
            }
        }
        stk.push(s);
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    For (i, 1, n) {
        char prev, next;
        std::cin >> prev;
        std::cin >> next;
        addEdge(prev, next);
        ++deg[prev];
        ++deg[next];
        __MIN_NODE = std::min(__MIN_NODE, std::min(prev, next));
        __MAX_NODE = std::max(__MAX_NODE, std::max(prev, next));
    }
    int odd = 0;
    char start = 0;
    for (char i = __MIN_NODE; i <= __MAX_NODE; ++i) {
        if (deg[i] != 0 && deg[i] % 2 == 1) {
            if (!start) start = i;
            ++odd;
        }
    }
    if (!start) start = __MIN_NODE;
    if (odd && odd != 2) {
    	// 注意不要忘了判无解
        std::cout << "No Solution" << std::endl;
        return 0;
    }
    Hierholzer(start);
    while (!stk.empty()) {
        std::cout << stk.top();
        stk.pop();
    }
    return 0;
}