Cod sursa(job #2126628)

Utilizator retrogradLucian Bicsi retrograd Data 9 februarie 2018 19:48:52
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;

struct Kosaraju {
    int n, ccs;
    vector<vector<int>> G, T, R;
    vector<int> stk, vis, comp;
    
    Kosaraju(int n) : n(n), G(n), T(n), vis(n), comp(n) {}

    void AddEdge(int a, int b) {
        G[a].push_back(b);
        T[b].push_back(a);
    }

    void dfs1(int node) {
        vis[node] = 1;
        for (auto vec : G[node])
            if (vis[vec] == 0)
                dfs1(vec);
        stk.push_back(node);
    }
    void dfs2(int node, int cc) {
        vis[node] = 2;
        comp[node] = cc;
        for (auto vec : T[node])
            if (vis[vec] == 1)
                dfs2(vec, cc);
    }

    vector<int> Solve() {
        for (int node = 0; node < n; ++node) {
            if (vis[node] == 0)
                dfs1(node);
        }
        reverse(stk.begin(), stk.end());
        for (auto node : stk) {
            if (vis[node] == 1)
                dfs2(node, ccs++);
        }
        return comp;
    }

    vector<vector<int>> BuildCondensation() {
        Solve();
        vector<vector<int>> R(ccs);
        for (int node = 0; node < n; ++node) {
            for (auto vec : G[node]) {
                if (comp[vec] != comp[node]) {
                    R[comp[node]].push_back(comp[vec]);
                }
            }
        }
        for (int i = 0; i < ccs; ++i) {
            sort(R[i].begin(), R[i].end());
            R[i].erase(unique(R[i].begin(), R[i].end()), R[i].end());
        }
        return R;
    }
};

struct Mine {
    int pos, rad, cost;
    bool operator<(const Mine& oth) const {
        return pos < oth.pos;
    }
};

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");

    int n, m; cin >> n >> m;
    Kosaraju ctc(n);

    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        ctc.AddEdge(a - 1, b - 1);
    }

    auto comp = ctc.Solve();
    vector<vector<int>> nodes(n + 1);

    int ccs = 0;
    for (int i = 0; i < n; ++i) {
        nodes[comp[i]].push_back(i);
        ccs = max(ccs, comp[i] + 1);
    }

    cout << ccs << endl;
    for (int i = 0; i < ccs; ++i) {
        for (auto x : nodes[i]) 
            cout << x + 1 << " ";
        cout << endl;
    }
    return 0;
}