Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //kosaraju for oriented
- #include<iostream>
- #include<fstream>
- #include<vector>
- using namespace std;
- vector<vector<int>> g;
- vector<vector<int>> t;
- vector<int>minus_;
- vector<int>plus_;
- int n, m;
- vector<vector<int>> keep_components;
- void read()
- {
- ifstream in("file.txt");
- if (!in.is_open())
- cout << "unable to open the file\n";
- else
- {
- in >> n >> m;
- g.resize(n + 1);
- for (int i = 0; i <= n; i++)
- g[i].assign(n + 1, 0);
- int x, y;
- minus_.assign(n + 1, 0);
- plus_.assign(n + 1, 0);
- for (int i = 0; i<m; i++)
- {
- in >> x >> y;
- g[x][y] = 1;
- }
- }
- }
- void for_minus(int source)
- {
- minus_[source] = 1;
- for (int i = 1; i <= n; i++)
- if (minus_[i] == 0 && g[source][i] == 1)
- for_minus(i);
- }
- void for_plus(int source)
- {
- plus_[source] = 1;
- for (int i = 1; i <= n; i++)
- if (plus_[i] == 0 && t[source][i] == 1)
- for_plus(i);
- }
- void make_transpuse()
- {
- t.resize(n + 1);
- for (int i = 0; i <= n; i++)
- t[i].assign(n + 1, 0);
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (g[i][j] == 1)
- t[j][i] = 1;
- }
- void kosaraju()
- {
- make_transpuse();
- int count_ = 0;
- for (int i = 1; i <= n; i++)
- {
- minus_.assign(n + 1, 0);
- plus_.assign(n + 1, 0);
- for_minus(i);
- for_plus(i);
- keep_components.resize(count_ + 1);
- for (int ii = 1; ii <= n; ii++)
- if (minus_[ii] == 1 && plus_[ii] == 1)
- keep_components[count_].push_back(ii);
- count_++;
- }
- }
- void print()
- {
- int i = 0;
- while(i<keep_components.size()-1)
- {
- for (int j = 0; j<keep_components[i].size(); j++)
- cout << keep_components[i][j] << " ";
- cout << endl;
- int delete_ = 1, nr_rows = 0;
- while (delete_ == 1)
- {
- for (int j = 0; j<keep_components[i].size() && delete_ == 1; j++)
- if (keep_components[i][j] != keep_components[i+1][j])
- delete_ = 0;
- if (delete_ == 1)
- nr_rows++;
- if(i<keep_components.size()-2)
- i++;
- else break;
- }
- i++;
- }
- }
- int main()
- {
- read();
- kosaraju();
- print();
- return 0;
- }
- /*
- 8 14
- 1 2
- 2 3
- 2 7
- 2 8
- 3 4
- 3 6
- 4 3
- 4 5
- 5 4
- 5 6
- 6 7
- 7 6
- 8 7
- 8 1
- should print:
- 1 2 8
- 3 4 5
- 6 7
- */
Add Comment
Please, Sign In to add comment