Advertisement
tumaryui

Untitled

Jul 9th, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("avx,avx2,fma")
  4. //#pragma GCC optimization ("unroll-loops")
  5.  
  6. #define int long long
  7. #define pb push_back
  8. #define all(s) s.begin(),s.end()
  9. #define pii pair<int,int>
  10. #define fr first
  11. #define sc second
  12. #define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  13. #define endl "\n"
  14. #define no cout << "NO" << endl;
  15. #define yes cout << "YES" << endl;
  16.  
  17. using namespace std;
  18.  
  19. const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7, logn = 23;
  20. const double pi = acos(-1);
  21.  
  22. vector<int> gr[N], tgr[N];
  23. vector<int> order, comp;
  24. int vis[N];
  25.  
  26. void dfs1(int v) {
  27. vis[v] = 1;
  28. for(auto to: gr[v]) {
  29. if(!vis[to]) {
  30. dfs1(to);
  31. }
  32. }
  33. order.pb(v);
  34. }
  35.  
  36. void dfs2(int v) {
  37. vis[v] = 1;
  38. comp.pb(v);
  39. for(auto to: tgr[v]) {
  40. if(!vis[to]) {
  41. dfs2(to);
  42. }
  43. }
  44. }
  45.  
  46. void solve() {
  47. //soln
  48. int n, m;
  49. cin >> n >> m;
  50.  
  51. while(m--) {
  52. int l, r;
  53. cin >> l >> r;
  54. gr[l].pb(r);
  55. tgr[r].pb(l);
  56. }
  57.  
  58. for(int i = 1; i <= n; i++) {
  59. if(!vis[i]) {
  60. dfs1(i);
  61. }
  62. }
  63. for(int i = 1; i <= n; i++) {
  64. vis[i] = 0;
  65. }
  66. reverse(all(order));
  67. for(auto it: order) {
  68. if(!vis[it]) {
  69. dfs2(it);
  70. for(auto v: comp) {
  71. cout << v << " ";
  72. }
  73. cout << endl;
  74. comp.clear();
  75. }
  76. }
  77. }
  78. main() {
  79. bst;
  80. int t = 1;
  81. //cin >> t;
  82. while(t--) {
  83. solve();
  84. }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement