fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Order of characters:
bdacefghijklmnopqrstuvwxyz
https://ideone.com/7oyrRn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!