fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3. #include <stack>
  4. #include <map>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. class Graph
  10. {
  11.     Graph (){}
  12.     int V;
  13.  
  14.     vector < list <int> > adj;
  15.  
  16.     void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
  17. public:
  18.     Graph(int V);
  19.  
  20.  
  21.     void addEdge(int v, int w);
  22.  
  23.     void topologicalSort();
  24. };
  25.  
  26. Graph::Graph(int V)
  27. {
  28.     this->V = V;
  29.     this->adj.resize (V, list <int> ());
  30. }
  31.  
  32. void Graph::addEdge(int v, int w)
  33. {
  34.     if (v > V)
  35.         Graph (v);        
  36.     adj[v].push_back(w);
  37. }
  38.  
  39. void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
  40. {
  41.     visited[v] = true;
  42.  
  43.     list<int>::iterator i;
  44.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  45.         if (!visited[*i])
  46.             topologicalSortUtil(*i, visited, Stack);
  47.  
  48.     Stack.push(v);
  49. }
  50.  
  51. void Graph::topologicalSort()
  52. {
  53.     stack<int> Stack;
  54.  
  55.     bool *visited = new bool[V];
  56.     for (int i = 0; i < V; i++)
  57.         visited[i] = false;
  58.  
  59.     for (int i = 0; i < V; i++)
  60.       if (visited[i] == false)
  61.         topologicalSortUtil(i, visited, Stack);
  62.  
  63.     while (Stack.empty() == false)
  64.     {
  65.         cout << Stack.top() << " ";
  66.         Stack.pop();
  67.     }
  68. }
  69.  
  70. int main()
  71. {
  72.     char alf [26];
  73.     map <char, int> sym;
  74.     for (char a = 'a' ; a <= 'z' ; a ++)
  75.         alf [a - 'a'] = a;
  76.     Graph g (0);
  77.     int n, k = 0;
  78.     cin >> n;
  79.     string prev;
  80.     cin >> prev;
  81.     for (int i = 0 ; i < n - 1 ; i ++)
  82.     {
  83.         string curr;
  84.         cin >> curr;
  85.         for (size_t i = 0 ; i < min (prev.size (), curr.size ()) ; i ++)
  86.             if (prev [i] != curr [i])
  87.             {
  88.                 if (sym.find (prev [i]) == sym.end ())
  89.                 {
  90.                     sym [prev [i]] = k ++;
  91.                 }
  92.                 if (sym.find (curr [i]) == sym.end ())
  93.                 {
  94.                     sym [curr [i]] = k ++;
  95.                 }
  96.                 g.addEdge (sym [prev [i]], sym [curr [i]]);
  97.             }
  98.     }
  99.     cout << "Following is a Topological Sort of the given graph \n";
  100.     g.topologicalSort();
  101.  
  102.     return 0;
  103. }
Runtime error #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
3
ac
pa
mc
stdout
copy 
Standard output is empty
https://ideone.com/R7dLcK
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!