fork(1) download
copy 
  1. //By prj22
  2. #include<iostream>
  3. #include<queue>
  4. #include<stack>
  5. #include<algorithm>
  6. #include<set>
  7. #include<cstdio>
  8.  
  9. class graph
  10. {
  11. 	//The class represents a directed graph
  12. 	public :
  13. 		std::vector< std::vector<int> > adj ;  //The adjacencly list for the graph
  14. 		int v ;  //The number of vertices
  15. 		int *indegree ; //The array to store the indegree of vertices
  16.  
  17.  
  18. 		//Vertices are assumed to be starting with number 1
  19.  
  20. 		graph(int v)
  21. 		{
  22. 			this->v = v ; //Assigning the number of vertices
  23.  
  24. 			//Allocating memory to arrays
  25. 			indegree = new int[v+1] ;
  26.  
  27. 			//Initialising the adjacency list
  28. 			for(int i=0 ; i<=v ; i++)
  29. 			{
  30. 				std::vector<int> data ;
  31. 				adj.push_back(data);
  32. 				indegree[i] = 0 ;  //Initialisation
  33. 			}
  34.  
  35. 		}
  36.  
  37. 		void addEdge(int u , int v)
  38. 		{
  39. 			adj.at(u).push_back(v);   //adding the edge u-->v
  40. 			indegree[v]++ ;  //Incrementing the indegree of v
  41. 		}
  42.  
  43. 		void toposort()
  44. 		{
  45. 			std::set<int> q ;  //Creating a set do that always smallest vertex is popped first
  46.  
  47. 			//Inserting in queue the vertices with indegree 0 (vertex indexing starting from 1)
  48.  
  49. 			for(int i=1 ; i<=v ; i++)
  50. 			  if(indegree[i] == 0)
  51. 			    q.insert(i);
  52.  
  53. 			int count = 0 ; //To count the number of vertices arranged in topological order
  54. 			std::vector<int> topo_order ;  //The vector to store the topological order of vertices
  55.  
  56. 			while(!q.empty())
  57. 			{
  58. 				int vertex = *q.begin() ;  //Getting the first element of the set
  59. 				q.erase(q.begin());
  60. 				topo_order.push_back(vertex);  //Adding the vertex to the ordering
  61.  
  62. 				//Iterating through all the neighbours of the vertex popped, decrementing their indegree by 1
  63. 				//and if their indegree becomes 0, they are pushed onto queue
  64.  
  65. 				std::vector<int> neighbours = adj.at(vertex);
  66. 				std::vector<int>::iterator it ;
  67. 				for(it = neighbours.begin() ; it!=neighbours.end() ; ++it)
  68. 				{
  69. 					indegree[(*it)]--;
  70. 					if(indegree[(*it)] == 0)
  71. 					  q.insert(*it);
  72. 				}
  73.  
  74.  
  75. 				count++; //Incrementing the count of vertex added to topological order
  76. 			}
  77.  
  78. 			if(count != v)  //Then all the vertex have not beem emtered and there is a cycle in the directed graph
  79. 			  printf("Sandro fails.\n");
  80. 			else
  81. 			{
  82. 				for(int i=0 ; i<topo_order.size() ; ++i)
  83. 				  printf("%d ",topo_order[i]);
  84. 				printf("\n");
  85. 			}
  86. 		}	
  87. };
  88.  
  89. int main()
  90. {
  91. 	int n , m , u , v ;
  92. 	scanf("%d%d",&n,&m);
  93. 	graph g(n);
  94.  
  95. 	for(int i=0 ; i<m ; i++)
  96. 	{
  97. 		scanf("%d%d",&u,&v);
  98. 		g.addEdge(u,v);
  99. 	}
  100. 	g.toposort();
  101. 	return 0 ;
  102. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
8 9
1 4
1 2
4 2
4 3
3 2
5 2
3 5
8 2
8 6
stdout
copy 
1 4 3 5 7 8 2 6
https://ideone.com/l3Ynrz
language:
C++14 (gcc 8.3)
created:
6 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!