algorithms/coderun/9325.cpp at master · crystarm/algorithms · GitHub

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// https://coderun.yandex.ru/problem/airline-tickets
// DFS (iterative with stack) + tree traversal (acyclic graph) + path reconstruction

#include <bits/stdc++.h>
using namespace std;

typedef string str;
typedef vector<str> vs;
typedef unordered_set<str> uss;

#define sz(x) (int)((x).size())
#define rsr(v,n) (v).reserve(n)
#define pb push_back
#define ppb pop_back
#define ins insert

#define fi first
#define se second

vs findPath(const str& from, const str& to,
            const function<vs(const str&)>& fetchFlights)
{
    if(from == to) return {from};

    struct frm { str u; int i; vs kids; bool ldd; }; typedef vector<frm> vfrm;

    vfrm st;
    vs path;
    uss vis;

    st.pb({from, 0, {}, 0});
    path.pb(from);
    vis.ins(from);

    while(!st.empty())
    {
        frm &top = st.back();

        if(top.u == to) return path;

        if(!top.ldd)
        {
            top.kids = fetchFlights(top.u);
            top.i = 0;
            top.ldd = 1;
        }

        if(top.i >= sz(top.kids))
        {
            st.ppb();
            path.ppb();
            continue;
        }

        str v = top.kids[top.i++];
        if(vis.count(v)) continue;

        vis.insert(v);
        st.pb({v, 0, {}, 0});
        path.pb(v);
    }

    return {};
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    vs t;
    str s;
    while(cin >> s) t.pb(s);
    if(t.empty()) return 0;

    auto is_int = [&](const str& x)
    {
        if(x.empty()) return 0;
        int i = 0;
        if(x[0] == '-')
        {
            if(sz(x) == 1) return 0;
            i = 1;
        }
        for(; i < sz(x); i++) if(!isdigit((unsigned char)x[i])) return 0;
        return 1;
    };

    str from, to;
    vector<pair<str,str>> e;

    if(is_int(t[0]))
    {
        int m = stoi(t[0]);
        if(sz(t) == 1 + 2 * m + 2)
        {
            for(int i = 0; i < m; i++) e.pb({t[1 + 2 * i], t[1 + 2 * i + 1]});
            from = t[1 + 2 * m];
            to = t[1 + 2 * m + 1];
        }
    }

    if(from.empty() && sz(t) >= 3 && is_int(t[2]))
    {
        int m = stoi(t[2]);
        if(sz(t) == 3 + 2 * m)
        {
            from = t[0];
            to = t[1];
            for(int i = 0; i < m; i++) e.pb({t[3 + 2 * i], t[3 + 2 * i + 1]});
        }
    }

    if(from.empty() && sz(t) >= 2 && (sz(t) - 2) % 2 == 0)
    {
        from = t[0];
        to = t[1];
        for(int i = 2; i < sz(t); i += 2) e.pb({t[i], t[i + 1]});
    }

    if(from.empty() && sz(t) >= 2 && (sz(t) - 2) % 2 == 0)
    {
        from = t[sz(t) - 2];
        to = t[sz(t) - 1];
        for(int i = 0; i + 1 < sz(t) - 2; i += 2) e.pb({t[i], t[i + 1]});
    }

    unordered_map<str, vs> g;
    for(auto &p : e) g[p.fi].pb(p.se);

    function<vs(const str&)> fetchFlights = [&](const str& u) -> vs
    {
        auto it = g.find(u);
        if(it == g.end()) return {};
        return it->second;
    };

    vs ans = findPath(from, to, fetchFlights);

    for(int i = 0; i < sz(ans); i++)
    {
        if(i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}