Cod sursa(job #3227224)

Utilizator lucamLuca Mazilescu lucam Data 28 aprilie 2024 14:53:29
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

struct G {
    vector<vector<int>> adj, radj;
    int n, m;
};

G read_graph() {
    G ret;
    in >> ret.n >> ret.m;
    ret.adj.resize(ret.n);
    ret.radj.resize(ret.n);
    for (int i = 0; i < ret.m; i++) {
        int u, v;
        in >> u >> v;
        --u, --v;
        ret.adj[u].push_back(v);
        ret.radj[v].push_back(u);
    }
    return ret;
}

struct SCCS {
    vector<vector<int>> comps;
    vector<int> comp_map;
};

void topsort_from(G &g, int u, vector<char> &vis, vector<int> &order) {
    stack<int> s;
    s.push(u);
    vis[u] = 1;
    while (!s.empty()) {
        int u = s.top();
        for (int v : g.adj[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                s.push(v);
            }
        }
        if (s.top() == u) {
            s.pop();
            order.push_back(u);
        }
    }
}

void discover_component(G &g, int u, SCCS &sccs) {
    int comp_id = sccs.comps.size();
    sccs.comps.push_back({});
    stack<int> s;
    s.push(u);
    sccs.comp_map[u] = comp_id;
    sccs.comps[comp_id].push_back(u);
    while (!s.empty()) {
        int u = s.top();
        for (int v : g.radj[u]) {
            if (sccs.comp_map[v] == -1) {
                sccs.comp_map[v] = comp_id;
                sccs.comps[comp_id].push_back(v);
                s.push(v);
            }
        }
        if (s.top() == u) {
            s.pop();
        }
    }
}

SCCS find_sccs(G &g) {
    vector<char> vis(g.n);
    vector<int> order;
    for (int i = 0; i < g.n; i++) {
        if (!vis[i]) {
            topsort_from(g, i, vis, order);
        }
    }
    SCCS ret;
    ret.comp_map.resize(g.n, -1);
    reverse(order.begin(), order.end());
    for (auto u : order) {
        if (ret.comp_map[u] != -1) {
            continue;
        }
        discover_component(g, u, ret);
    }
    return ret;
}

int main() {
    G g = read_graph();
    SCCS sccs = find_sccs(g);
    out << sccs.comps.size() << '\n';
    for (auto &comp : sccs.comps) {
        for (int u : comp) {
            out << u + 1 << ' ';
        }
        out << '\n';
    }
}