SDA - hw10 - task3

#include <iostream>
#include <cmath>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <climits>


using namespace std;

stack<char> res;
int idx = 25;
unordered_map<int, vector<int>> graph;
bool visited[26]{ false };

size_t firstDifferentIdx(string prev, string next) {
    size_t idx = 0;
    while (prev[idx] == next[idx] && idx < prev.length() && idx < next.length()) {
        idx++;
    }
    return idx;
}

void dfs(int val) {
    visited[val] = true;
    auto neighbours = graph[val];
    for (int i = 0; i < neighbours.size(); i++)
    {
        if (!visited[neighbours[i]])
            dfs(neighbours[i]);
    }
    res.push(val + 'a');
}


int main()
{
    int n;
    cin >> n;
    string prev, next;
    cin >> prev;
    for (int i = 1; i < n; i++) {
        cin >> next;
        size_t diffIdx = firstDifferentIdx(prev, next);
        if (diffIdx < prev.length()) {
            graph[prev.at(diffIdx) - 'a'].push_back(next.at(diffIdx) - 'a');
        }
        prev = next;
    }

    for (auto i : graph)
    {
        if (!visited[i.first])
            dfs(i.first);
    }

    while(!res.empty()){
        cout << res.top() << " ";
        res.pop();
    }
}