bhupixb

Strongly Connected components

Jul 18th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 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 int long long
  7. #define F first
  8. #define S second
  9. #define rep(i,a,n) for (int i = a; i <= n; ++i)
  10. #define fo(i, n) for (int i = 1; i <= n; ++i)
  11. #define all(v) v.begin(), v.end()
  12. #define pb push_back
  13. #define P pair < int, int >
  14. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  15. #define E cout << '\n'
  16. const int N = 1e5 + 5;
  17. int vis[N];
  18.  
  19. vector < int > g[N], revg[N], v;
  20.  
  21. void dfs(int node) {
  22. vis[node] = 1;
  23. for(auto i : g[node])
  24. if(!vis[i])
  25. dfs(i);
  26. v.push_back(node);
  27. }
  28. vector < int > let;
  29. void revdfs(int node) {
  30. vis[node] = true;
  31. let.push_back(node);
  32. for(auto i : revg[node])
  33. if(!vis[i])
  34. revdfs(i);
  35. }
  36. inline void solve() {
  37. int k, n, m, ans(0), l, r;
  38. cin >> n;// number of nodes
  39. cin >> m;// number of edges
  40. for(int i = 1; i <= m; ++i) {
  41. cin >> l >> r;
  42. g[l].push_back(r);
  43. revg[r].push_back(l);
  44. }
  45. for(int i = 1; i <= n; ++i) {
  46. if(!vis[i])
  47. dfs(i);
  48. }
  49. memset(vis, 0, sizeof vis);
  50. cout << "Nodes with strongly connected components are \n";
  51. while(!v.empty()) {
  52. int i = v.back();
  53. if(!vis[i]) {
  54. revdfs(i);
  55. int ans = 0;
  56. for (auto i : let) {
  57. cout << i << ' ';
  58. }
  59. let.clear();
  60. }
  61. v.pop_back();
  62. cout << '\n';
  63. }
  64. }
  65. signed main(){
  66. fast;
  67. solve();
  68. return 0;
  69. }
Add Comment
Please, Sign In to add comment