Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int MAX_LEN = (int)1e6 + 10;
- const int M = 255;
- const int N = M + M;
- struct Edge {
- int to;
- string word;
- Edge(int to, const string &s)
- : to(to), word(s) {
- }
- Edge() {
- }
- };
- vector<Edge> g[N];
- vector<string> result;
- char buffer[MAX_LEN];
- int degIn[N], degOut[N];
- bool used[N];
- void addEdge() {
- Edge e;
- e.word = buffer;
- e.to = e.word.back() + M;
- g[buffer[0] + M].push_back(e);
- ++degIn[e.to];
- ++degOut[buffer[0] + M];
- }
- void input() {
- int m;
- scanf("%d\n", &m);
- for (int i = 0; i < m; ++i) {
- gets(buffer);
- addEdge();
- }
- }
- void dfsCheck(int v) {
- used[v] = true;
- for (size_t i = 0; i < g[v].size(); ++i) {
- if (!used[g[v][i].to]) {
- dfsCheck(g[v][i].to);
- }
- }
- }
- bool checkConnectivity() {
- int c = 0;
- for (int i = 0; i < N; ++i) {
- if (degIn[i] + degOut[i] > 0 && !used[i]) {
- dfsCheck(i);
- ++c;
- }
- }
- return c < 2;
- }
- bool checkDegrees() {
- for (int i = 0; i < N; ++i) {
- if (degIn[i] != degOut[i]) {
- return false;
- }
- }
- return true;
- }
- void dfs(int v, const string &word) {
- while (g[v].size() > 0) {
- Edge e = g[v].back();
- g[v].pop_back();
- dfs(e.to, e.word);
- }
- result.push_back(word);
- }
- void getEulerCicle() {
- for (int i = 0; i < N; ++i) {
- if (degIn[i]) {
- dfs(i, "");
- break;
- }
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- input();
- if (!checkConnectivity() || !checkDegrees()) {
- printf("No");
- return 0;
- }
- puts("Yes");
- getEulerCicle();
- reverse(result.begin(), result.end());
- for (size_t i = 1; i < result.size(); ++i) {
- puts(result[i].c_str());
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment