fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,m;
  5. void topsort(vector<int>*g, int *indegree,vector<int>&ans)
  6. {
  7.  
  8.    queue<int>q;
  9.    for(int i=1;i<=n;i++)
  10.    {
  11.        if(indegree[i]==0)
  12.        {
  13.            q.push(i);
  14.        }
  15.    }
  16.    while(!q.empty())
  17.    {
  18.        int cur=q.front();
  19.        q.pop();
  20.        ans.push_back(cur);
  21.        for(auto x: g[cur])
  22.        {
  23.            indegree[x]--;
  24.            if(indegree[x]==0) q.push(x);
  25.        }
  26.    }
  27.    for(auto x: ans)
  28.     {
  29.         cout<<x<< " ";
  30.     }
  31.     cout<<endl;
  32.  
  33. }
  34.  
  35. int main()
  36. {
  37.  
  38.     cin>>n>>m;
  39.  
  40.     vector<int>g[n+1];
  41.     int indegree[n+1]={0};
  42.     for(int i=0;i<m;i++)
  43.     {
  44.         int u,v;
  45.         cin>>u>>v;
  46.         g[u].push_back(v);
  47.         indegree[v]++;
  48.     }
  49.     vector<int>ans;
  50.     topsort(g,indegree,ans);
  51.  
  52. //    for(int i=1;i<=n;i++)
  53. //    {
  54. //        cout<<i<< " "<<indegree[i]<<endl;
  55. //    }
  56. }
  57. /*
  58. 7 12
  59. 1 4
  60. 1 5
  61. 1 7
  62. 4 5
  63. 3 5
  64. 2 5
  65. 5 6
  66. 6 7
  67. 3 4
  68. 2 3
  69. 2 6
  70. 5 7
  71. */
  72.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/MDxax4
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
2 days 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!