Cod sursa(job #2924836)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 11 octombrie 2022 20:11:05
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.75 kb
#include <utility>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
class graph {
    int n, m;
    std::vector<int> sel;
    std::vector<std::vector<int>> nodes_list;
    vector<int> topological_order;
    bool has_cycle = false;
    vector<vector<int>> strongly_connected_components;

    void auxiliary_dfs (int start, vector<int> &DF);
    void auxiliary_dfs2 (int start);

public:
    graph(int n, int m, std::vector<std::vector<int>> nodes_list);
    graph(const vector<vector<int>>& edges, int n, int m);
    graph() : n(0), m(0) {}

    void dfs (const int &start);
    int number_of_components();
    vector<vector<int>> get_bipartition ();
    bool check_bipartite ();
    bool check_dfs (vector<int> permutation);
    vector<int> findOrder(vector<vector<int>>& edges);
    vector<int> get_cycle();

    vector<vector<int>> get_strongly_connected_components();

    void
    auxiliary_dfs3(int start, vector<bool> &on_stack, vector<int> &low_link_value, stack<int> &stack, vector<int> &id,
                   int &current_id);
};

graph::graph (int n, int m, std::vector<std::vector<int>> nodes_list) : n(n), m(m), nodes_list(std::move(nodes_list)){
    sel.resize(n + 1, 0);
}

graph::graph(const vector<vector<int>>& edges, int n, int m = 0) : n(n), m(m) {
    if (!m) m = edges.size();
    nodes_list.resize(n + 1);
    sel.resize(n + 1, 0);
    for (auto edge : edges) {
        nodes_list[edge[0]].push_back(edge[1]);
//        nodes_list[edge[1]].push_back(edge[0]);
    }
}

void graph::dfs (const int &start) {
    sel[start] = 1;
    for (auto vecin : nodes_list[start]) {
        if (!sel[vecin]) dfs(vecin);
    }
}

int graph::number_of_components () {
    int number_of_components = 0;
    for (int i = 1; i <= n; ++i) {
        if (!sel[i]) {
            ++number_of_components;
            dfs(i);
        }
    }
    sel.resize(n + 1, 0);
    return number_of_components;
}

vector<vector<int>> graph::get_bipartition () {
    vector<int> color(n + 1, -1);
    vector<int> color0;    /// nodurile colorate cu culoarea 0
    vector<int> color1;    /// nodurile colorate cu culoarea 1

    queue<int> BF;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == -1) {
            BF.push(i);
            color[i] = 0;
            color0.push_back(i);

            while (!BF.empty()) {
                int current = BF.front();
                BF.pop();

                for (auto nbh : nodes_list[current]) {
                    if (color[current] == color[nbh]) return {{},{}};
                    if (color[nbh] == -1) {
                        color[nbh] = 1 - color[current];
                        if (color[nbh]) color1.push_back(nbh);
                        else color0.push_back(nbh);
                        BF.push(nbh);
                    }
                }
            }
        }
    }

    vector<vector<int>> split(2);
    split[0] = color0;
    split[1] = color1;
    return split;
}

bool graph::check_bipartite() {
    auto split = get_bipartition();
    return !(split[0].empty() && split[1].empty());
}

bool graph::check_dfs (vector<int> permutation) {
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i)
        pos[permutation[i]] = i;

    for (int i = 1; i <= n; ++i) {
        sort(nodes_list[i].begin(), nodes_list[i].end(), [&] (int a, int b) { return pos[a] < pos[b]; });
    }

    vector<int> DF;
    auxiliary_dfs (permutation[0], DF);
    sel.resize(n + 1, 0);
    return (DF == permutation);
}

void graph::auxiliary_dfs(int start, vector<int> &DF) {
    DF.push_back(start);
    sel[start] = 1;
    for (auto nbh : nodes_list[start]) {
        if (!sel[nbh])
            auxiliary_dfs(nbh, DF);
    }
}

void graph::auxiliary_dfs2 (int start) {
    sel[start] = 1;
    for (auto nbh : nodes_list[start]) {
        if (!sel[nbh]) dfs(nbh);
        else if (find(topological_order.begin(), topological_order.end(), nbh) == topological_order.end()) {
            has_cycle = true;
            topological_order.push_back(nbh);
            return;
        }
    }
    topological_order.push_back(start);
}

vector<int> graph::findOrder(vector<vector<int>>& edges) {
    for (auto edge : edges)
        nodes_list[edge[1]].push_back(edge[0]);

    sel.resize(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!sel[i])
            auxiliary_dfs2(i);
    }

    sel.resize(n + 1, 0);

    if (has_cycle) {
        topological_order.clear();
        return {};
    }

    reverse(topological_order.begin(), topological_order.end());
    return topological_order;
}

vector<int> graph::get_cycle () {
    sel.resize(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        if (!sel[i])
            dfs(i);
    }

    sel.resize(n + 1, 0);

    if (has_cycle) {
        reverse(topological_order.begin(), topological_order.end());
        return topological_order;
    }
    return {};
}

void graph::auxiliary_dfs3 (int start, vector<bool> &on_stack, vector<int> &low_link_value, stack<int> &stack, vector<int> &id, int &current_id) {
    stack.push(start);
    on_stack[start] = true;
    id[start] = low_link_value[start] = ++current_id;
    for (auto nbh : nodes_list[start]) {
        if (id[nbh] == -1)
            auxiliary_dfs3(nbh, on_stack, low_link_value, stack, id, current_id);
        if (on_stack[nbh])
            low_link_value[start] = min(low_link_value[start], low_link_value[nbh]);

    }
    if (id[start] == low_link_value[start]) {
        vector<int> found_component;
        int top = stack.top();
        while (top != start) {
            found_component.push_back(top);
            on_stack[top] = false;
            low_link_value[top] = id[start];
            stack.pop();
            top = stack.top();
        }
        found_component.push_back(start);
        stack.pop();
        strongly_connected_components.push_back(found_component);
    }
}

vector<vector<int>> graph::get_strongly_connected_components() {
    vector<int> low_link_value(n + 1, 0);
    vector<int> id(n + 1, -1);
    stack<int> stack;
    vector<bool> on_stack(n + 1, false);
    int current_id = 0;

    for (int i = 1; i <= n; ++i)
        if (id[i] == -1)
            auxiliary_dfs3(i, on_stack, low_link_value, stack, id, current_id);

    return strongly_connected_components;
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    vector<vector<int>> edges;
//    edges = {{1 ,2},{2, 6},{6, 7},{7, 6},{3, 1},{3, 4},{2, 3},{4, 5},{5, 4},{6, 5},{5, 8},{8, 7}};
    int n, m;
    fin >> n >> m;
    while (m--) {
        int a, b;
        fin >> a >> b;
        edges.push_back({a, b});
    }
    graph meow2(edges, n, m);
    auto x = meow2.get_strongly_connected_components();
    fout << x.size() << '\n';
    for (const auto& comp : x) {
        for (auto it : comp)
            fout << it << " ";
        fout << '\n';
    }

    return 0;
}