Advertisement
Guest User

Untitled

a guest
Dec 13th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. typedef long long Long;
  3.  
  4. #define MAX 100001
  5.  
  6. #define PB push_back
  7. #define MP make_pair
  8. #define FF first
  9. #define SS second
  10.  
  11. #define PII pair<int, int>
  12. #define VI vector<int>
  13.  
  14. #define FOR(a, n) for(int i=a;i<n;i++)
  15. #define FORn(a, n) for(int i=a;i<=n;i++)
  16.  
  17. #define mm(a, n) memset(a, n, sizeof(a))
  18.  
  19. #define PF printf
  20. #define PC putchar
  21. #define GC getchar
  22.  
  23. #define printCase cout<<"Case "<<i<<": "vagfol
  24. #define printCaseC PF("Case %d: ", i)
  25.  
  26. #define II() ({int a; scanf("%d", &a); a;})
  27. #define LI() ({Long a; scanf("%I64d", &a); a;})
  28. #define DI() ({double a; scanf("%lf", &a); a;})
  29.  
  30. #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
  31. //double pi=atan(1)*4;
  32.  
  33. using namespace std;
  34. vector<vector<int>> G(MAX), GT(MAX);
  35. int n, e;
  36. void Read()
  37. {
  38. cin>>n>>e;
  39. FOR(0, e)
  40. {
  41. int u, v;
  42. cin>>u>>v;
  43. G[u].PB(v);
  44. GT[v].PB(u);
  45. }
  46. }
  47. stack<int> s;
  48. int vis[MAX];
  49. void dfs(int u)
  50. {
  51. vis[u]=1;
  52. FOR(0, G[u].size())
  53. {
  54. int v=G[u][i];
  55. if(vis[v]==0)
  56. dfs(v);
  57. }
  58. s.push(u);
  59. }
  60. vector<int> res;
  61. void dfs2(int u)
  62. {
  63. vis[u]=1;
  64. res.PB(u);
  65. FOR(0, GT[u].size())
  66. {
  67. int v=GT[u][i];
  68. if(vis[v]==0)
  69. dfs2(v);
  70. }
  71. }
  72. void SCC()
  73. {
  74. FOR(0, n)
  75. {
  76. if(vis[i]==0)
  77. dfs(i);
  78. }
  79. mm(vis, 0);
  80. int cnt=0;
  81. vector<vector<int>> t;
  82. for(int i=1; !s.empty(); i++)
  83. {
  84.  
  85. int u=s.top();
  86. s.pop();
  87. if(vis[u]==0)
  88. {
  89. dfs2(u);
  90. t.PB(res);
  91. res.clear();
  92. cnt++;
  93. }
  94. }
  95. FOR(0, t.size())
  96. {
  97. for(int j=0; j<t[i].size();j++)
  98. cout<<t[i][j]<<" ";
  99. cout<<endl;
  100. }
  101. cout<<"\nTotal: "<<cnt<<" strongly connected components\n";
  102. }
  103. int main()
  104. {
  105. #ifndef ONLINE_JUDGE
  106. freopen("input.txt", "r", stdin);
  107. freopen("output.txt", "w", stdout);
  108. #else
  109. #endif
  110. /* *******Bismillahir Rahmanir Rahim **** */
  111. // FastIO;
  112. Read();
  113. SCC();
  114. return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement