Cod sursa(job #2192877)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 7 aprilie 2018 16:28:58
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include<iostream>
#include<vector>
#include<stack>
#include<unordered_map>
#include<unordered_set>
using namespace std;

typedef unordered_map<int, vector<int> > graph;

void dfs_inner(graph &G, int node, unordered_set<int> &used, vector<int> &comp) {
    used.insert(node);
    comp.push_back(node);
    for (const auto &child : G[node]) {
        if (used.find(child) == used.end()) {
            dfs_inner(G, child, used, comp);
        }
    }
}

vector<vector<int> > dfs(graph &G, const vector<int> &top_sort) {
    unordered_set<int> used;
    vector<vector<int> > ans;
    for (const auto &node : top_sort) {
        if (used.find(node) == used.end()) {
            vector<int> comp;
            dfs_inner(G, node, used, comp);
            ans.push_back(comp);
        }
    }
    return ans;
}

void topological_sort_inner(graph &G, int node, unordered_set<int> &used, stack<int> &st) {
    used.insert(node);
    for (const auto &child : G[node]) {
        if (used.find(child) == used.end()) {
            topological_sort_inner(G, child, used, st);
        }
    }
    st.push(node);
}

vector<int> topological_sort(graph &G) {
    unordered_set<int> used;
    stack<int> st;
    for (const auto &it : G) {
        if (used.find(it.first) == used.end()) {
            topological_sort_inner(G, it.first, used, st);
        }
    }
    vector<int> ans;
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }
    return ans;
}

graph transpose(graph &G) {
    graph T;
    for (const auto &it : G) {
        for (const auto &child : G[it.first]) {
            T[child].push_back(it.first);
        }
    }
    return T;
}

vector<vector<int> > scc(graph &G) {
    graph T = transpose(G);
    vector<int> top_sort = topological_sort(G);
    return dfs(T, top_sort);
}


int main () {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    int n, m, x, y, i;
    graph G;

    cin >> n >> m;
    for (i = 0; i < m; i++) {
        cin >> x >> y;
        G[x].push_back(y);
    }

    vector<vector<int> > components = scc(G);

    cout << components.size() << endl;
    for (const auto &comp : components) {
        for (const auto &node : comp) {
            cout << node << ' ';
        }
        cout << endl;
    }

    return 0;
}