fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11.  
  12. const int N = 1e5 + 5; 
  13.  
  14. int n, m;  
  15. vector<int> adj[N]; 
  16.  
  17. /* Kahn's algorithm */
  18. int in_deg[N];  
  19. vector<int> topo;   
  20.  
  21. void topoSort() {
  22. 	queue<int> q;  
  23. 	for (int u = 1; u <= n; u++) {
  24. 		if (in_deg[u] == 0) q.push(u); 
  25. 	}
  26.  
  27. 	while (!q.empty()) {
  28. 		int u = q.front(); q.pop(); 
  29.  
  30. 		topo.push_back(u);   
  31.  
  32. 		for (int v : adj[u]) {
  33. 			in_deg[v]--; 
  34. 			if (in_deg[v] == 0) q.push(v); 
  35. 		}
  36. 	}
  37. }
  38.  
  39. int main() {
  40. 	ios::sync_with_stdio(false); 
  41. 	cin.tie(nullptr); 	
  42. 	cin >> n >> m; 
  43.  
  44. 	for (int i = 0; i < m; i++) {
  45. 		int u, v; 
  46. 		cin >> u >> v; 
  47. 		adj[u].push_back(v); 
  48. 		in_deg[v]++; 
  49. 	}
  50.  
  51. 	topoSort(); 
  52.  
  53. 	if (topo.size() < n) {
  54. 		cout << "IMPOSSIBLE" << '\n'; 
  55. 		return 0; 
  56. 	}
  57.  
  58. 	for (int u : topo) cout << u << ' '; 
  59. }
Success #stdin #stdout 0.01s 5960KB
comments (?)
stdin 
5 3
1 2
3 1
4 5
stdout 
3 4 1 5 2
https://ideone.com/ONY4OY
language:
C++14 (gcc 8.3)
created:
289 days 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!