Grupe X - 6.6.5 / pag 174

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector < pair < char , char > > a;
    for(int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        a.emplace_back(s[0], s[s.size() - 1]);
    }
    vector < int > dp(N, INF);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < i; ++j)
            if(a[i].first == a[j].second && dp[i] > dp[j] + 1)
                dp[i] = dp[j] + 1;
        if(dp[i] == INF)
            dp[i] = 1;
    }
    int ans = 1;
    for(int x : dp)
        if(x != INF)
            ans = max(ans, x);
    cout << ans << '\n';
    char last = '$';
    vector < int > sol;
    for(int i = ans; i > 0; --i) {
        int poz = -1;
        for(int j = 0; j < N; ++j)
            if(dp[j] == i && (last == '$' || a[j].second == last)) {
                poz = j;
                last = a[j].first;
                break;
            }
        sol.emplace_back(poz + 1);
    }
    reverse(sol.begin(), sol.end());
    for(int x : sol)
        cout << x << '\n';
}