//
// main.cpp
// Alien Dictionary
//
// Created by Himanshu on 13/09/21.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 26;
void topologicalSort (int x, vector<int> graph[], int vis[], stack<int> &st) {
vis[x] = 1;
for (int i=0; i<graph[x].size(); i++) {
int j = graph[x][i];
if (vis[j] == 0) {
topologicalSort(j, graph, vis, st);
}
}
st.push(x);
}
void createGraph (vector<int> graph[N], vector<string> words) {
for (int i = 0; i < words.size()-1; i++) {
string word1 = words[i], word2 = words[i+1];
for (int j = 0; j < word1.size() && j < word2.size(); j++) {
// Add an edge for every mismatched character from word1[j]
// to word2[j]
if (word1[j] != word2[j]) {
graph[word1[j]-'a'].push_back(word2[j]-'a');
break;
}
}
}
}
int main() {
stack<int> st;
vector<string> words = {"baa", "abcd", "abca", "cab", "cad"};
vector<int> graph[N];
createGraph(graph, words);
int vis[N];
for (int i=0; i<N; i++) {
vis[i] = 0;
}
for (int i=N-1; i>=0; i--) {
if (vis[i] == 0) {
topologicalSort(i, graph, vis, st);
}
}
cout<<"Order of characters:"<<endl;
while(!st.empty()) {
char ch = st.top() + 'a';
cout<<ch;
st.pop();
}
cout<<endl;
return 0;
}
Ly8KLy8gIG1haW4uY3BwCi8vICBBbGllbiBEaWN0aW9uYXJ5Ci8vCi8vICBDcmVhdGVkIGJ5IEhpbWFuc2h1IG9uIDEzLzA5LzIxLgovLwoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gMjY7CgoKdm9pZCB0b3BvbG9naWNhbFNvcnQgKGludCB4LCB2ZWN0b3I8aW50PiBncmFwaFtdLCBpbnQgdmlzW10sIHN0YWNrPGludD4gJnN0KSB7CiAgICB2aXNbeF0gPSAxOwogICAgZm9yIChpbnQgaT0wOyBpPGdyYXBoW3hdLnNpemUoKTsgaSsrKSB7CiAgICAgICAgaW50IGogPSBncmFwaFt4XVtpXTsKICAgICAgICBpZiAodmlzW2pdID09IDApIHsKICAgICAgICAgICAgdG9wb2xvZ2ljYWxTb3J0KGosIGdyYXBoLCB2aXMsIHN0KTsKICAgICAgICB9CiAgICB9CiAgICBzdC5wdXNoKHgpOwp9Cgp2b2lkIGNyZWF0ZUdyYXBoICh2ZWN0b3I8aW50PiBncmFwaFtOXSwgdmVjdG9yPHN0cmluZz4gd29yZHMpIHsKICAgIAogICAgZm9yIChpbnQgaSA9IDA7IGkgPCB3b3Jkcy5zaXplKCktMTsgaSsrKSB7CiAgICAgICBzdHJpbmcgd29yZDEgPSB3b3Jkc1tpXSwgd29yZDIgPSB3b3Jkc1tpKzFdOwogICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCB3b3JkMS5zaXplKCkgJiYgaiA8IHdvcmQyLnNpemUoKTsgaisrKSB7CiAgICAgICAgICAgLy8gQWRkIGFuIGVkZ2UgZm9yIGV2ZXJ5IG1pc21hdGNoZWQgY2hhcmFjdGVyIGZyb20gd29yZDFbal0KICAgICAgICAgICAvLyB0byB3b3JkMltqXQogICAgICAgICAgIGlmICh3b3JkMVtqXSAhPSB3b3JkMltqXSkgewogICAgICAgICAgICAgICBncmFwaFt3b3JkMVtqXS0nYSddLnB1c2hfYmFjayh3b3JkMltqXS0nYScpOwogICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICB9CiAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgc3RhY2s8aW50PiBzdDsKICAgIHZlY3RvcjxzdHJpbmc+IHdvcmRzID0geyJiYWEiLCAiYWJjZCIsICJhYmNhIiwgImNhYiIsICJjYWQifTsKICAgIHZlY3RvcjxpbnQ+IGdyYXBoW05dOwogICAgY3JlYXRlR3JhcGgoZ3JhcGgsIHdvcmRzKTsKICAgIAogICAgaW50IHZpc1tOXTsKICAgIGZvciAoaW50IGk9MDsgaTxOOyBpKyspIHsKICAgICAgICB2aXNbaV0gPSAwOwogICAgfQogICAgCiAgICBmb3IgKGludCBpPU4tMTsgaT49MDsgaS0tKSB7CiAgICAgICAgaWYgKHZpc1tpXSA9PSAwKSB7CiAgICAgICAgICAgIHRvcG9sb2dpY2FsU29ydChpLCBncmFwaCwgdmlzLCBzdCk7CiAgICAgICAgfQogICAgfQoKICAgIGNvdXQ8PCJPcmRlciBvZiBjaGFyYWN0ZXJzOiI8PGVuZGw7CiAgICB3aGlsZSghc3QuZW1wdHkoKSkgewogICAgICAgIGNoYXIgY2ggPSBzdC50b3AoKSArICdhJzsKICAgICAgICBjb3V0PDxjaDsKICAgICAgICBzdC5wb3AoKTsKICAgIH0KICAgIGNvdXQ8PGVuZGw7CiAgICByZXR1cm4gMDsKfQoK