monyca98

kosaraju for oriented

May 25th, 2018
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. //kosaraju for oriented
  2.  
  3. #include<iostream>
  4. #include<fstream>
  5. #include<vector>
  6.  
  7. using namespace std;
  8.  
  9. vector<vector<int>> g;
  10. vector<vector<int>> t;
  11. vector<int>minus_;
  12. vector<int>plus_;
  13. int n, m;
  14. vector<vector<int>> keep_components;
  15. void read()
  16. {
  17.     ifstream in("file.txt");
  18.     if (!in.is_open())
  19.         cout << "unable to open the file\n";
  20.     else
  21.     {
  22.         in >> n >> m;
  23.         g.resize(n + 1);
  24.         for (int i = 0; i <= n; i++)
  25.             g[i].assign(n + 1, 0);
  26.         int x, y;
  27.         minus_.assign(n + 1, 0);
  28.         plus_.assign(n + 1, 0);
  29.         for (int i = 0; i<m; i++)
  30.         {
  31.             in >> x >> y;
  32.             g[x][y] = 1;
  33.         }
  34.     }
  35. }
  36.  
  37. void for_minus(int source)
  38. {
  39.     minus_[source] = 1;
  40.     for (int i = 1; i <= n; i++)
  41.         if (minus_[i] == 0 && g[source][i] == 1)
  42.             for_minus(i);
  43. }
  44. void for_plus(int source)
  45. {
  46.     plus_[source] = 1;
  47.     for (int i = 1; i <= n; i++)
  48.         if (plus_[i] == 0 && t[source][i] == 1)
  49.             for_plus(i);
  50. }
  51. void make_transpuse()
  52. {
  53.     t.resize(n + 1);
  54.     for (int i = 0; i <= n; i++)
  55.         t[i].assign(n + 1, 0);
  56.     for (int i = 1; i <= n; i++)
  57.         for (int j = 1; j <= n; j++)
  58.             if (g[i][j] == 1)
  59.                 t[j][i] = 1;
  60. }
  61. void kosaraju()
  62. {
  63.     make_transpuse();
  64.     int count_ = 0;
  65.     for (int i = 1; i <= n; i++)
  66.     {
  67.         minus_.assign(n + 1, 0);
  68.         plus_.assign(n + 1, 0);
  69.         for_minus(i);
  70.         for_plus(i);
  71.         keep_components.resize(count_ + 1);
  72.  
  73.         for (int ii = 1; ii <= n; ii++)
  74.             if (minus_[ii] == 1 && plus_[ii] == 1)
  75.                 keep_components[count_].push_back(ii);
  76.         count_++;
  77.     }
  78. }
  79.  
  80. void print()
  81. {
  82.  
  83.     int i = 0;
  84.     while(i<keep_components.size()-1)
  85.     {
  86.         for (int j = 0; j<keep_components[i].size(); j++)
  87.             cout << keep_components[i][j] << " ";
  88.         cout << endl;
  89.         int delete_ = 1, nr_rows = 0;
  90.         while (delete_ == 1)
  91.         {
  92.             for (int j = 0; j<keep_components[i].size() && delete_ == 1; j++)
  93.                 if (keep_components[i][j] != keep_components[i+1][j])
  94.                     delete_ = 0;
  95.             if (delete_ == 1)
  96.                 nr_rows++;
  97.             if(i<keep_components.size()-2)
  98.                 i++;
  99.             else break;
  100.         }
  101.  
  102.         i++;
  103.     }
  104. }
  105. int main()
  106. {
  107.     read();
  108.     kosaraju();
  109.     print();
  110.     return 0;
  111. }
  112.  
  113.  
  114. /*
  115.  
  116. 8 14
  117. 1 2
  118. 2 3
  119. 2 7
  120. 2 8
  121. 3 4
  122. 3 6
  123. 4 3
  124. 4 5
  125. 5 4
  126. 5 6
  127. 6 7
  128. 7 6
  129. 8 7
  130. 8 1
  131.  
  132.  
  133. should print:
  134. 1 2 8
  135. 3 4 5
  136. 6 7
  137. */
Add Comment
Please, Sign In to add comment