Laba 4

gistfile1.txt

#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);
}