fork download
copy 
  1. // REF: geeksforgeeks.org/topological-sorting-indegree-based-solution/
  2. #include <iostream>
  3. #include <vector>
  4. #include <list>
  5. #include <queue>
  6. using namespace std;
  7. class Graph {
  8. private:
  9.     unsigned vertices;
  10.     std::list<unsigned> *adj_list;
  11. public:
  12.     Graph(unsigned);
  13.     ~Graph();
  14.     void add_edge(unsigned, unsigned);
  15.     string topsort();
  16. };
  17.  
  18. Graph::Graph(unsigned v)
  19. {
  20.     vertices = v;
  21.     adj_list = new std::list<unsigned>[v];
  22. }
  23.  
  24. Graph::~Graph()
  25. {
  26.     delete [] adj_list;
  27. }
  28.  
  29. void Graph::add_edge(unsigned src, unsigned dst)
  30. {
  31.     adj_list[src].push_back(dst);
  32. }
  33.  
  34. string Graph::topsort()
  35. {
  36.     /* create a vector to store in-degree of all vertices
  37.      *  vector sized `vertices'  all initialized to zero
  38.      * */
  39.     std::vector<unsigned> in_degree(vertices, 0);
  40.     std::string a,b;
  41.  
  42.     /* traverse adjacency lists to fill up in_degree[]
  43.      *  this step takes O(V+E) time
  44.      * */
  45.     std::list<unsigned>::iterator it;
  46.     for (unsigned i = 0; i < vertices; i++)
  47.         for (it = adj_list[i].begin(); it != adj_list[i].end(); it++)
  48.             in_degree[*it]++;
  49.  
  50.     /* create a queue and enqueue all vertices with in-degree 0 */
  51.     std::queue<unsigned> que;
  52.     for (unsigned i = 0; i < vertices; i++){
  53.         if (in_degree[i] == 0){
  54.         que.push(i);  
  55.         b += char(65+i);
  56.         cout<<"b"<<b<<endl;
  57.         } 
  58.     }
  59.     if (que.size()>=2){
  60.         a += b;
  61.     }
  62.     b = "";
  63.  
  64.  
  65.     /* bookkepping for count of visited vertices */
  66.     unsigned visited = 0;
  67.     /* vector to store topological sort result */
  68.     std::vector<unsigned> top_order;
  69.  
  70.     while (que.size()) {
  71.         /* extract front of queue(dequeue) and add it to result vector */
  72.         unsigned top = que.front();
  73.         que.pop();
  74.         top_order.push_back(top);
  75.  
  76.         /* iterate all its(top's) adjacent vertices and
  77.          *  decrease their in-degree by 1
  78.          * */
  79.         for (it = adj_list[top].begin(); it != adj_list[top].end(); it++)
  80.             /* once in-degree becomes zero  push it to queue */
  81.             if (--in_degree[*it] == 0)
  82.                 que.push(*it);
  83.  
  84.         visited++;      /* update visited vertices */
  85.     }
  86.  
  87.     /* if visited not equal to #vertices  there is a cycle */
  88.     if (visited != vertices) {
  89.         std::cerr << "[ERROR] There exists a cycle in the graph\n";
  90.         return "bkchodi";
  91.     }
  92.  
  93.     /* print out topological sort result */
  94.     // for (unsigned i = 0; i < vertices; i++)
  95.     //     std::cout << top_order[i] << ' ';
  96.     // std::cout << '\n';
  97.     return a;
  98. }
  99.  
  100. int main()
  101. {
  102.     int n,m;
  103.     cin>>n>>m;
  104.     Graph g(n);
  105.     // g.topsort();
  106.     string str,ans;
  107.  
  108.     for (int i=0;i<m;i++){
  109.         cin>>str;
  110.         for (int index = 0; index < str.length()-2; index+=2)
  111.         {
  112.             int src = int(str[index])-65;
  113.             int dest = int(str[index+2])-65;
  114.             g.add_edge(src,dest);
  115.         }
  116.     }
  117.  
  118.     ans = g.topsort();
  119.     if(ans.length())
  120.         for(int i=0;i<ans.length();i++)
  121.             cout<<ans[i]<<" ";
  122.     else
  123.         cout<<"N/A"<<endl;
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
8 3
D,C,E,F,G,H
C,A,E
D,C,B,E
stdout
copy 
bD
N/A
https://ideone.com/suKL4o
language:
C++14 (gcc 8.3)
created:
5 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!