bhupixb

Strongly Connected components

Jul 23rd, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  1. // I can't tell you what it really is,
  2. // I can only tell you what it feels like.
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5.  
  6. #define pb push_back
  7. #define E cout << '\n'
  8. #define rep(i,a,n) for (int i = a; i <= n; ++i)
  9. #define int long long
  10. const int mod = 1e9 + 7;
  11. const int N = 3e5 + 5;
  12.  
  13. vector < int > v[N], fin;
  14. vector < int > revg[N];
  15. bool vis[N];
  16.  
  17. void dfs(int node) {
  18. vis[node] = 1;
  19. // Dfs in graph G
  20. for (auto i : v[node]) {
  21. if (!vis[i]) {
  22. dfs(i);
  23. }
  24. }
  25. fin.pb(node);// According to finishing time
  26. }
  27.  
  28. void dfs_rev(int node) {
  29. vis[node] = 1;
  30. cout << node << ' ';
  31. // Dfs in graph with inverted Edges
  32. for (auto i : revg[node]) {
  33. if (!vis[i]) {
  34. dfs_rev(i);
  35. }
  36. }
  37. }
  38.  
  39. inline void solve() {
  40. int n, m, l, r, ways = 1;
  41. long long ans(0);
  42. cin >> n >> m;
  43. // n = number of nodes, m = number of edges (directed)
  44.  
  45. rep(i,1,m) {
  46. cin >> l >> r;
  47. v[l].pb(r); // Add direct edge
  48. revg[r].pb(l); // Add flipped edge
  49. }
  50.  
  51. rep(i,1,n) {
  52. if (!vis[i]) {
  53. dfs(i);
  54. }
  55. }
  56.  
  57. // Reverse according to highest finishing time
  58. reverse(fin.begin(), fin.end());
  59.  
  60. memset(vis, 0, sizeof(vis));
  61.  
  62. for (auto i : fin) {
  63. if (!vis[i]) {
  64. dfs_rev(i);
  65. cout << '\n';
  66. // Maintain a vector if component element required
  67. }
  68. }
  69.  
  70. }
  71.  
  72. signed main() {
  73. ios_base::sync_with_stdio(0);
  74. cin.tie(NULL);
  75. cout.tie(NULL);
  76. int t = 1;
  77. //cin >> t; while(t--)
  78. solve();
  79. return 0;
  80. }
Add Comment
Please, Sign In to add comment