fork(2) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<fstream>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<cstdlib>
  7. #include<cmath>
  8. #include<vector>
  9. #include<climits>
  10. #include<string>
  11. #include<stack>
  12. #include<queue>
  13. #include<map>
  14. #include<list>
  15. using namespace std;
  16.  
  17. vector<int> dependences;
  18.  
  19. class compare{
  20. 	public:
  21. 		bool operator()(const int &l , const int &r){
  22. 			if(dependences[l] == dependences[r]){
  23. 				return l > r; 
  24. 			}else if(dependences[l] > dependences[r]){
  25. 				return true;
  26. 			}else{
  27. 				return false;
  28. 			}
  29.  
  30. 		}
  31. };
  32.  
  33. int main(){
  34. 	int N , M;
  35. 	scanf("%d %d" , &N , &M);
  36. 	vector<list<int> > graph(N+1);
  37. 	vector<list<int> > fathers(N+1);
  38. 	dependences.resize(N+1);
  39. 	priority_queue<int , vector<int> , compare> pq;
  40. 	for(int i = 1;i<=N ;i++){
  41. 		dependences[i] = 0;
  42. 	}
  43. 	for(int i = 0;i<M;i++){
  44. 		int n , num;
  45. 		scanf("%d %d", &n , &num);
  46. 		while(num--){
  47. 			int v;
  48. 			scanf("%d" , &v);
  49. 			graph[n].push_back(v);
  50. 			fathers[v].push_back(n);
  51. 			dependences[n]++;
  52. 		}
  53. 	}
  54. 	for(int i = 1;i<= N;i++){
  55. 		if(dependences[i] == 0){
  56. 			pq.push(i);
  57. 		}
  58. 	}
  59. 	for(int i = 1;i<= N;i++){
  60. 		int v;
  61. 		v = pq.top();
  62. 		pq.pop();
  63. 		printf("%d " , v);
  64. 		for(list<int>::const_iterator it = fathers[v].begin() ; it != fathers[v].end() ; it++){
  65. 			dependences[*it]--;
  66. 			if(dependences[*it] == 0){
  67. 				pq.push(*it);
  68. 			}
  69. 		} 
  70. 	} 
  71.  
  72. }
  73.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
9 5 
1 4 5 4 3 2 
4 1 6 
5 1 9 
3 1 7 
2 1 8
stdout
copy 
6 4 7 3 8 2 9 5 1
https://ideone.com/iH8yVe
language:
C++ (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!