fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/algorithm>
  3. #include <ext/numeric>
  4.  
  5. using namespace std;
  6. using namespace __gnu_cxx;
  7.  
  8. #define endl '\n'
  9.  
  10. int main()
  11. {
  12. 	ios_base::sync_with_stdio(0);
  13. 	cin.tie(0);
  14.  
  15. 	int n, m;
  16. 	cin >> n >> m;
  17.  
  18. 	vector<int> indeg(n);
  19. 	vector<vector<int>> g(n);
  20.  
  21. 	for (int i = 0; i < m; ++i)
  22. 	{
  23. 		int u, v;
  24. 		cin >> u >> v;
  25. 		--u, --v;
  26.  
  27. 		++indeg[v];
  28. 		g[u].push_back(v);
  29. 	}
  30.  
  31. 	set<int> S;
  32. 	for (int i = 0; i < n; ++i)
  33. 		if (indeg[i] == 0)
  34. 			S.insert(i);
  35.  
  36. 	int total = 0;
  37. 	vector<int> ans;
  38.  
  39. 	while (total < n)
  40. 	{
  41. 		if (S.empty())
  42. 		{
  43. 			cout << "Sandro fails." << endl;
  44. 			return 0;
  45. 		}
  46.  
  47. 		int u = *S.begin();
  48. 		S.erase(S.begin());
  49.  
  50. 		ans.push_back(u);
  51.  
  52. 		for (auto v : g[u])
  53. 			if (--indeg[v] == 0)
  54. 				S.insert(v);
  55.  
  56. 		total += 1;
  57. 	}
  58.  
  59. 	for (auto x : ans)
  60. 		cout << x+1 << " ";
  61. 	cout << endl;
  62.  
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0s 3280KB
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/4TbCgM
language:
C++14 (gcc 8.3)
created:
8 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!