fork download
  1. //
  2. // main.cpp
  3. // Alien Dictionary
  4. //
  5. // Created by Himanshu on 13/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <stack>
  11. using namespace std;
  12. const int N = 26;
  13.  
  14.  
  15. void topologicalSort (int x, vector<int> graph[], int vis[], stack<int> &st) {
  16. vis[x] = 1;
  17. for (int i=0; i<graph[x].size(); i++) {
  18. int j = graph[x][i];
  19. if (vis[j] == 0) {
  20. topologicalSort(j, graph, vis, st);
  21. }
  22. }
  23. st.push(x);
  24. }
  25.  
  26. void createGraph (vector<int> graph[N], vector<string> words) {
  27.  
  28. for (int i = 0; i < words.size()-1; i++) {
  29. string word1 = words[i], word2 = words[i+1];
  30. for (int j = 0; j < word1.size() && j < word2.size(); j++) {
  31. // Add an edge for every mismatched character from word1[j]
  32. // to word2[j]
  33. if (word1[j] != word2[j]) {
  34. graph[word1[j]-'a'].push_back(word2[j]-'a');
  35. break;
  36. }
  37. }
  38. }
  39. }
  40.  
  41. int main() {
  42. stack<int> st;
  43. vector<string> words = {"baa", "abcd", "abca", "cab", "cad"};
  44. vector<int> graph[N];
  45. createGraph(graph, words);
  46.  
  47. int vis[N];
  48. for (int i=0; i<N; i++) {
  49. vis[i] = 0;
  50. }
  51.  
  52. for (int i=N-1; i>=0; i--) {
  53. if (vis[i] == 0) {
  54. topologicalSort(i, graph, vis, st);
  55. }
  56. }
  57.  
  58. cout<<"Order of characters:"<<endl;
  59. while(!st.empty()) {
  60. char ch = st.top() + 'a';
  61. cout<<ch;
  62. st.pop();
  63. }
  64. cout<<endl;
  65. return 0;
  66. }
  67.  
  68.  
Success #stdin #stdout 0.01s 5364KB
stdin
Standard input is empty
stdout
Order of characters:
bdacefghijklmnopqrstuvwxyz