a_pramanik

Finding Strongly connected components

Aug 23rd, 2016
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. //-_-
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define ll long long int
  7. #define inf 2000000000
  8. #define pi (2.0*acos(0.0))
  9. #define vsort(v)   sort(v.begin(),v.end())
  10. #define ull unsigned long long int
  11. #define mem(a, b) memset(a, b, sizeof a)
  12. #define cf 100009
  13. vector<int>a[100], cmp[100], b[100];
  14.  
  15. int vis[100], mrk;
  16. stack<int>st;
  17. void f(int u)
  18. {
  19.     vis[u]++;
  20.     for(int i=0; i<a[u].size(); i++){
  21.         int y = a[u][i];
  22.         if(vis[y]==0){
  23.             f(y);
  24.         }
  25.     }
  26.     st.push(u);
  27. }
  28.  
  29. void dfs(int u)
  30. {
  31.     vis[u]++;
  32.     cmp[mrk].pb(u);
  33.  
  34.     for(int i=0; i<b[u].size(); i++){
  35.         int y = b[u][i];
  36.         if(vis[y]==0){
  37.             dfs(y);
  38.         }
  39.     }
  40.  
  41. }
  42.  
  43. int main()
  44. {
  45.     int n, i, j, k, x, y, m;
  46.  
  47.     while(scanf("%d%d", &n, &m)==2){
  48.  
  49.         for(i=1; i<=m; i++){
  50.             scanf("%d%d", &x, &y);
  51.             a[x].pb(y);
  52.             b[y].pb(x);
  53.         }
  54.  
  55.         mem(vis, 0);
  56.  
  57.         for(i=1; i<=n; i++){
  58.             if(vis[i]==0){
  59.                 f(i);
  60.             }
  61.         }
  62.  
  63.         mem(vis,0);
  64.         mrk=0;
  65.  
  66.         while(!st.empty()){
  67.             x=st.top();
  68.             st.pop();
  69.             if(vis[x]==0){
  70.                 ++mrk;
  71.                 dfs(x);
  72.             }
  73.         }
  74.         cout<<mrk<<endl;
  75.         for(i=1; i<=mrk; i++){
  76.             for(j=0; j<cmp[i].size(); j++){
  77.                 printf("%d ",cmp[i][j]);
  78.             }
  79.             printf("\n");
  80.         }
  81.  
  82.         for(i=1; i<=n; i++){
  83.                 a[i].clear();
  84.                 b[i].clear();
  85.         }
  86.     }
  87.     return 0;
  88. }
Add Comment
Please, Sign In to add comment