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