洛谷 P1341 无序字母对

本题涉及欧拉回路/欧拉路径。
参考:https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html

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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
struct e {
    char t;
    int bool_v;
    e(char t1, int v1) { t = t1; bool_v = v1; }
    bool operator < (const e& e2) const {
        return t < e2.t;
    }
};
vector<e> edge[130];
vector<char> path;
int degree[130];
bool visited[3000];
void dfs(char node) {
    for (int i = 0; i < edge[node].size(); i++) {
        if (visited[edge[node][i].bool_v])continue;
        visited[edge[node][i].bool_v] = true;
        dfs(edge[node][i].t);
    }
    path.push_back(node);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        degree[c1]++;
        degree[c2]++;
        edge[c1].push_back(e(c2, i));
        edge[c2].push_back(e(c1, i));
    }
    for (char i = 0; i <= 126; i++) {
        if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end());
    }
    int odd = 0;//奇
    char s = -1;
    for (char i = 127; i >= 0; i--) {
        if (degree[i] % 2 == 0 && degree[i] > 0) {
            if (odd == 0)s = i;
        }
        else if (degree[i] % 2 == 1) {
            odd++;
            s = i;
        }
    }
    if (!(odd == 0 || odd == 2)) {
        cout << "No Solution";
        return 0;
    }
    dfs(s);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
    }
}

可能确实不大好理解这个代码,然后就做了一个简易的例子来说明这个问题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注