Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- bool had_circle(const vector<vector<int>>&, vector<char>&, int);
- bool t_sort(const vector<vector<int>>&, vector<int>&, vector<char>&, int);
- void find_strong_linked_components(const vector<vector<int>>&, vector<int>&, vector<char>& used, int);
- int main() {
- int n, m;
- cin >> n >> m;
- vector<vector<int>> g(n), gt(n);
- int u, v;
- for(int i = 0; i < m; i++) {
- cin >> u >> v;
- u--;
- v--;
- g[u].push_back(v);
- gt[v].push_back(u);
- }
- bool had_c = false;
- vector<char> du(n, 0);
- for(int i = 0; i < n; i++)
- if(du[i] == 0)
- if(had_circle(g, du, i) ) {
- had_c = true;
- break;
- }
- vector<int> list;
- du.assign(n, 0);
- for(int i = 0; i < n; i++)
- if(du[i] == 0)
- t_sort(g, list, du, i);
- reverse(list.begin(), list.end());
- if(!had_c) {
- cout << "Topological sort: " << endl;
- for (auto x: list)
- cout << x + 1 << " ";
- cout << endl;
- } else {
- cout << "We have circle" << endl;
- }
- // find strong linked components
- du.assign(n, 0);
- vector<int> component;
- int count = 0;
- for(int i = 0; i < n; i++)
- if(du[list[i]] == 0) {
- count++;
- find_strong_linked_components(gt, component, du, list[i]);
- // print component
- for(auto x: component)
- cout << x + 1 << " ";
- cout << endl;
- component.clear();
- }
- cout << "In result We have " << count << " strong linked components" << endl;
- return 0;
- }
- bool had_circle(const vector<vector<int>>& v, vector<char>& u, int k) {
- u[k] = 1;
- for(auto x: v[k])
- if(u[x] == 1)
- return true;
- else if(u[x] == 0)
- return had_circle(v, u, x);
- u[k] = 2;
- return false;
- }
- bool t_sort(const vector<vector<int>>& v, vector<int>& l, vector<char>& used, int k) {
- used[k] = 1;
- for(auto x: v[k])
- if(used[x] == 0)
- t_sort(v, l, used, x);
- l.push_back(k);
- }
- void find_strong_linked_components(const vector<vector<int>>& v, vector<int>& l, vector<char>& used, int k) {
- used[k] = 1;
- l.push_back(k);
- for(auto x: v[k])
- if(used[x] == 0)
- find_strong_linked_components(v, l, used, x);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement